oj.uz

Submission #63273

# Submission time Handle Problem Language Result Execution time Memory
63273 2018-08-01T08:19:51 Z 노영훈(#1832) Alternating Current (BOI18_alternating) C++11
0 / 100
 162 ms 71132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n, m;
struct line{
    int s, e, ans=-1, idx;
    void scan(){
        cin>>s>>e;
    }
    bool operator < (const line &l) const {
        return s<l.s || (s==l.s && e>l.e);
    }
} L[MX];

bool solve(){
    bool done[MX][2]={};

    priority_queue<pii> Q;
    for(int i=1, frt=0; i<=n; i++){
        while(frt<m && L[frt+1].s<=i) frt++, Q.push({L[frt].e, frt});
        for(int j=0; j<=1; j++){
            if(done[i][j]) continue;
            while(!Q.empty() && Q.top().first<i) Q.pop();
            if(Q.empty()) return false;
            int e,idx; tie(e,idx)=Q.top(); Q.pop();
            for(int x=i; x<=e; x++) done[x][j]=true;
            L[idx].ans=j;
        }
    }
    return true;
}

void solve3(){
    deque<int> A[MX];
    for(int i=1; i<=m; i++) A[L[i].s].push_back(i);
    deque<int> used;
    priority_queue<pii> Q;
    for(int i=1, r=0; i<=n; i++){
        for(int idx:A[i]) Q.push({L[idx].e + (i<=L[idx].e ? 0 : n), idx});
        if(i<=r) continue;
        pii now=Q.top(); Q.pop();
        r=now.first; used.push_back(now.second);
    }
    int cnt[MX]={};
    for(int x:used) for(int ii=L[x].s; ii<=L[x].e + (L[x].s<=L[x].e ? 0 : n); ii++)
        cnt[(ii-1)%n+1]++;
    bool out=false;
    for(int i=1; i<=n; i++) if(cnt[i]>=3) out=true;
    if(out) used.pop_front();
    for(int x:used) L[x].ans=1;
}

void show(){
    sort(L+1, L+m+1, [](line &a, line &b){ return a.idx<b.idx; });
    for(int i=1; i<=m; i++) cout<<max(0,L[i].ans);
    cout<<'\n';
}

bool is3(){
    int cnt[100010]={};
    for(int i=1; i<=m; i++){
        int s=L[i].s, e=L[i].e;
        if(s<=e){
            cnt[s]++, cnt[e+1]--;
        }
        else{
            cnt[1]++, cnt[s+1]--;
            cnt[e]++, cnt[n+1]--;
        }
    }
    for(int i=1, now=0; i<=n; i++){
        now+=cnt[i];
        if(now<3) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++) L[i].scan(), L[i].idx=i;
    sort(L+1, L+m+1);

    if(is3()) solve3(), show();

    if(!solve()){ cout<<"impossible\n"; return 0; }
    show();
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 69752 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 69752 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 69752 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 71132 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 69752 KB Expected EOF
2 Halted 0 ms 0 KB -