oj.uz

Submission #63185

# Submission time Handle Problem Language Result Execution time Memory
63185 2018-08-01T04:33:03 Z 노영훈(#1832) Alternating Current (BOI18_alternating) C++11
0 / 100
 67 ms 15000 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, j=0; i<=n; i++){
        while(j<n && L[j+1].s<=i) j++, Q.push({L[j].e, j});
        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 2168 KB Output is correct
2 Correct 4 ms 2228 KB Output is correct
3 Incorrect 5 ms 2260 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 2168 KB Output is correct
2 Correct 4 ms 2228 KB Output is correct
3 Incorrect 5 ms 2260 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 2168 KB Output is correct
2 Correct 4 ms 2228 KB Output is correct
3 Incorrect 5 ms 2260 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4320 KB Output is correct
2 Correct 13 ms 4412 KB Output is correct
3 Correct 20 ms 4412 KB Output is correct
4 Correct 26 ms 5544 KB Output is correct
5 Correct 63 ms 5668 KB Output is correct
6 Correct 42 ms 7152 KB Output is correct
7 Correct 53 ms 8008 KB Output is correct
8 Correct 9 ms 8968 KB Output is correct
9 Correct 10 ms 8968 KB Output is correct
10 Correct 66 ms 9088 KB Output is correct
11 Correct 47 ms 10228 KB Output is correct
12 Correct 53 ms 11144 KB Output is correct
13 Correct 24 ms 11980 KB Output is correct
14 Correct 26 ms 12116 KB Output is correct
15 Correct 67 ms 13144 KB Output is correct
16 Correct 33 ms 13784 KB Output is correct
17 Correct 65 ms 15000 KB Output is correct
18 Incorrect 38 ms 15000 KB 'impossible' claimed, but there is a solution
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

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