oj.uz

Submission #898442

# Submission time Handle Problem Language Result Execution time Memory
898442 2024-01-04T16:31:48 Z LucaIlie Event Hopping 2 (JOI21_event2) C++17
0 / 100
 3000 ms 5480 KB 
#include <bits/stdc++.h>

using namespace std;

struct event {
    int l, r;
};

const int MAX_N = 1e5;
event events[MAX_N + 1];

int main() {
    int n, k;

    cin >> n >> k;
    for ( int i = 1; i <= n; i++ )
        cin >> events[i].l >> events[i].r;

    vector<int> ans;
    for ( int i = 1; i <= n && k > 0; i++ ) {
        bool ok = true;
        for ( int j: ans ) {
            if ( !(events[j].r <= events[i].l || events[i].r <= events[j].l) )
                ok = false;
        }
        if ( !ok )
            continue;

        vector<event> queryEvents;
        for ( int j = i + 1; j <= n; j++ )
            queryEvents.push_back( events[i] );
        sort( queryEvents.begin(), queryEvents.end(), []( event a, event b ) {
            if ( a.r == b.r )
                return a.l < b.l;
            return a.r < b.r;
        } );

        int x = 0, t = 0;
        for ( event e: events ) {
            if ( e.l >= t ) {
                x++;
                t = e.r;
            }
        }
        if ( x >= k - 1 ) {
            ans.push_back( i );
            k--;
        }
    }

    if ( k > 0 ) {
        cout << -1;
        return 0;
    }
    for ( int i: ans )
        cout << i << "\n";

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 3085 ms 5480 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 3085 ms 5480 KB Time limit exceeded
5 Halted 0 ms 0 KB -