oj.uz

Submission #63275

# Submission time Handle Problem Language Result Execution time Memory
63275 2018-08-01T08:24:27 Z 노영훈(#1832) Alternating Current (BOI18_alternating) C++11
19 / 100
 79 ms 6576 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(){
    vector<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[MX]={};
    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(); return 0; }

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

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4600 KB Output is correct
2 Correct 5 ms 4600 KB Output is correct
3 Incorrect 4 ms 4600 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4600 KB Output is correct
2 Correct 5 ms 4600 KB Output is correct
3 Incorrect 4 ms 4600 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4600 KB Output is correct
2 Correct 5 ms 4600 KB Output is correct
3 Incorrect 4 ms 4600 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6028 KB Output is correct
2 Correct 4 ms 6028 KB Output is correct
3 Correct 15 ms 6028 KB Output is correct
4 Correct 20 ms 6028 KB Output is correct
5 Correct 50 ms 6028 KB Output is correct
6 Correct 39 ms 6028 KB Output is correct
7 Correct 53 ms 6028 KB Output is correct
8 Correct 7 ms 6028 KB Output is correct
9 Correct 5 ms 6028 KB Output is correct
10 Correct 64 ms 6028 KB Output is correct
11 Correct 42 ms 6028 KB Output is correct
12 Correct 47 ms 6028 KB Output is correct
13 Correct 4 ms 6028 KB Output is correct
14 Correct 5 ms 6028 KB Output is correct
15 Correct 60 ms 6028 KB Output is correct
16 Correct 22 ms 6028 KB Output is correct
17 Correct 79 ms 6028 KB Output is correct
18 Correct 57 ms 6576 KB Output is correct
19 Correct 7 ms 6576 KB Output is correct
20 Correct 71 ms 6576 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4600 KB Output is correct
2 Correct 5 ms 4600 KB Output is correct
3 Incorrect 4 ms 4600 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -