oj.uz

Submission #63186

# Submission time Handle Problem Language Result Execution time Memory
63186 2018-08-01T04:34:21 Z 노영훈(#1832) Alternating Current (BOI18_alternating) C++11
19 / 100
 78 ms 3876 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;
}

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(!solve()){ cout<<"impossible\n"; return 0; }
    sort(L+1, L+m+1, [](line &a, line &b){ return a.idx<b.idx; });
    for(int i=1; i<=m; i++) cout<<max(L[i].ans, 0);
    cout<<'\n';
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2040 KB Output is correct
2 Correct 4 ms 2152 KB Output is correct
3 Incorrect 4 ms 2152 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 2040 KB Output is correct
2 Correct 4 ms 2152 KB Output is correct
3 Incorrect 4 ms 2152 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 2040 KB Output is correct
2 Correct 4 ms 2152 KB Output is correct
3 Incorrect 4 ms 2152 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 48 ms 3320 KB Output is correct
2 Correct 6 ms 3320 KB Output is correct
3 Correct 22 ms 3320 KB Output is correct
4 Correct 22 ms 3320 KB Output is correct
5 Correct 64 ms 3320 KB Output is correct
6 Correct 37 ms 3320 KB Output is correct
7 Correct 78 ms 3320 KB Output is correct
8 Correct 6 ms 3320 KB Output is correct
9 Correct 5 ms 3320 KB Output is correct
10 Correct 74 ms 3320 KB Output is correct
11 Correct 40 ms 3320 KB Output is correct
12 Correct 49 ms 3320 KB Output is correct
13 Correct 7 ms 3320 KB Output is correct
14 Correct 6 ms 3320 KB Output is correct
15 Correct 61 ms 3684 KB Output is correct
16 Correct 33 ms 3684 KB Output is correct
17 Correct 59 ms 3684 KB Output is correct
18 Correct 66 ms 3684 KB Output is correct
19 Correct 8 ms 3684 KB Output is correct
20 Correct 78 ms 3876 KB Output is correct

Subtask #5
0 / 26.0

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