Submission #898442

#	Time	Username	Problem	Language	Result	Execution time	Memory
898442		LucaIlie	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	3085 ms	5480 KiB

event2

#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
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61