Submission #1118284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118284		Zero_OP	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	22 ms	1956 KiB

event2

#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" #x " = " << (x) << "]"

struct max_suffix_fenwick{
    vector<int> bit;
    max_suffix_fenwick(int n) : bit(n + 1, 0) {}

    void update(int i, int v){
        for(; i > 0; i -= i & (-i)) bit[i] = max(bit[i], v);
    }

    int query(int i){
        int best = 0;
        for(; i < (int)bit.size(); i += i & (-i)) best = max(best, bit[i]);
        return best;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.ans", "w", stdout);
#endif // LOCAL

    int N, K;
    cin >> N >> K;

    struct event{
        int l, r, id;
        event(int l, int r, int id) : l(l), r(r), id(id) {}
        bool operator < (const event& o){
            if(l != o.l) return l < o.l;
            if(r != o.r) return r < o.r;
            return id < o.id;
        }
    };

    vector<event> events;
    vector<int> v;
    for(int i = 0; i < N; ++i){
        int l, r;
        cin >> l >> r;
        events.push_back(event(l, r, i));
    }

    for(int mask = (1 << K) - 1; mask < (1 << N); ++mask) if(__builtin_popcount(mask) == K){
        vector<int> diff(20);
        for(int i = 0; i < N; ++i){
            if(mask >> i & 1){
                ++diff[events[i].l];
                --diff[events[i].r];
            }
        }

        bool ok = true;
        for(int i = 1; i < 20; ++i){
            diff[i] += diff[i - 1];
            if(diff[i] > 1){
                ok = false;
            }
        }

        if(ok){
            for(int i = 0; i < N; ++i){
                if(mask >> i & 1){
                    cout << i + 1 << '\n';
                }
            }
            return 0;
        }
    }

    cout << -1 <<'\n';

    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61