Submission #251903

#	Time	Username	Problem	Language	Result	Execution time	Memory
251903		jhnah917	Alternating Current (BOI18_alternating)	C++14	32 / 100	195 ms	2176 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];
bool chk[101010][2];

void naive(){
    for(int bit=0; bit<(1 << m); bit++){
        memset(chk, 0, sizeof chk);
        for(int i=1; i<=m; i++){
            int j = i-1;
            for(int k=a[i].s; ; k++){
                if(k > n) k = 1;
                chk[k][(bit >> j) & 1] = 1;
                if(k == a[i].e) break;
            }
        }
        int flag = 1;
        for(int i=1; i<=n; i++) flag &= (chk[i][0] & chk[i][1]);
        if(flag){
            for(int i=0; i<m; i++) cout << ((bit >> i) & 1);
            return;
        }
    }
    cout << "impossible";
}

vector<int> big;
int par[1010];

int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
void partition(){
    vector<Info> v; int ed = 0, idx = 0;
    for(int i=1; i<=m; i++){
        v.push_back(a[i]);
        if(a[i].s > a[i].e){
            ed = max(ed, a[i].e);
            if(ed == a[i].e) idx = i;
            v.back().e += n;
        }
    }
    sort(all(v));
    deque<Info> dq;
    iota(par, par+1010, 0);
    for(auto i : v){
        if(dq.empty() || dq.back().e < i.e) dq.push_back(i);
        else par[i.x] = dq.back().x;
    }
    while(dq.size() && dq.front().e <= ed) par[dq.front().x] = idx, dq.pop_front();
    sort(all(dq));
    for(auto i : dq) big.push_back(i.x);
    for(int i=1; i<=m; i++) par[i] = find(par[i]);
}

int even(){
    int pv = 0;
    for(auto i : big){
        ans[i] = (pv & 1); pv++;
    }
    for(int i=1; i<=m; i++){
        if(i == par[i]) continue;
        ans[i] = !ans[par[i]];
    }
    for(int i=1; i<=m; i++){
        int s = a[i].s, e = a[i].e;
        for(int j=s; ; j++){
            if(j > n) j = 1;
            chk[j][ans[i]] = 1;
            if(j == e) break;
        }
    }
    for(int i=1; i<=n; i++){
        if(!chk[i][0] || !chk[i][1]) return 0;
    }
    for(int i=1; i<=m; i++) cout << ans[i];
    return 1;
}

void subtask55(){
    partition();
    if(even()) return;
    big.push_back(big[0]);
    big.erase(big.begin());
    if(!even()) cout << "impossible";
}

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; }
    if(n <= 15 && m <= 15){ naive(); return 0; }
    if(n <= 1000 && m <= 1000){ subtask55(); return 0; }
    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: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26