Submission #251896

#	Time	Username	Problem	Language	Result	Execution time	Memory
251896		jhnah917	Alternating Current (BOI18_alternating)	C++14	0 / 100	31 ms	3064 KiB

alternating

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

struct Info{
    int s, e, x;
    Info() : Info(0, 0, 0) {}
    Info(int s, int e, int x) : s(s), e(e), x(x) {}
    bool operator < (const Info &t) const {
        if(s != t.s) return s < t.s;
        if(e != t.e) return e > t.e;
        return x < t.x;
    }
};

int n, m;
Info a[101010];
int ans[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1; i<=m; i++){ cin >> a[i].s >> a[i].e; a[i].x = i; }
    sort(a+1, a+m+1);
    int cnt0 = 0, cnt1 = 0;
    for(int i=1; i<=m; i++){
        int s = a[i].s, e = a[i].e, x = a[i].x;
        if(cnt0 < cnt1){
            if(cnt0 >= s-1) cnt0 = max(cnt0, e), ans[x] = 0;
        }else{
            if(cnt1 >= s-1) cnt1 = max(cnt1, e), ans[x] = 1;
        }
    }
    if(cnt0 < n || cnt1 < n){
        cout << "impossible"; return 0;
    }
    for(int i=1; i<=m; i++) cout << ans[i] << " ";
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26