oj.uz

Submission #648847

# Submission time Handle Problem Language Result Execution time Memory
648847 2022-10-08T13:53:15 Z fatemetmhr Alternating Current (BOI18_alternating) C++17
19 / 100
 38 ms 18176 KB 
// ~ Be Name Khoda ~

// Harf ke nazanim... 
// Zende bemoonim?
// Ya oonm na?


#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

int a[maxn5], b[maxn5];
bool have[2][maxn5];
int n, m;
bool ty[maxn5], mark[maxn5];
vector <int> seg[maxn5], ex;


inline void solve(){
    for(int i = 0; i < n; i++)
        seg[i].clear();
    ex.clear();
    for(int i = 0; i < m; i++) if(!mark[i]){
        seg[a[i] > b[i] ? 0 : a[i]].pb(i);
    }
    int id1 = -1, id2 = -1;
    for(int i = 0; i < n; i++){
        if(id1 != -1 && b[id1] < i)
            id1 = -1;
        if(id2 != -1 && b[id2] < i)
            id2 = -1;
        //cout << "here we go " << i << ' ' << id1 << ' ' << id2 << ' ' << have[1][i] << ' ' << have[0][i] << endl;
        while(!ex.empty() && b[ex.back()] < i)
            ex.pop_back();
        for(auto u : seg[i])
            ex.pb(u);
        if(id1 == -1 && !have[1][i]){
            if(ex.empty())
                return;
            id1 = ex.back();
            ty[id1] = true;
            ex.pop_back();
        }
        while(!ex.empty() && b[ex.back()] < i)
            ex.pop_back();
        if(id2 == -1 && !have[0][i]){
            if(ex.empty())
                return;
            id2 = ex.back();
            ty[id2] = false;
            ex.pop_back();
        }
    }
    for(int i = 0; i < m; i++)
        cout << ty[i];
    cout << endl;
    exit(0);
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }

    int blid = -1;

    for(int i = 0; i < m; i++) if(a[i] == 0 || a[i] > b[i])
        if(blid == -1 || a[blid] == 0 || a[blid] > a[i])
            blid = i;
    if(blid == -1){
        cout << "impossible\n";
        return 0;
    }

    //cout << "ok " << blid << endl;

    for(int i = 0; i < m; i++) if(i != blid && (a[i] == 0 || a[i] > b[i])){
        //cout << "check out " << i << ' ' << "wtf " << blid << endl;
        memset(mark, false, sizeof mark);
        mark[i] = true; ty[i] = 0; mark[blid] = true; ty[blid] = 1;
        memset(have, false, sizeof have);
        for(int j = a[i]; j != b[i]; j = (j + 1) % n)
            have[0][j] = true;
        have[0][b[i]] = true;
        int rbl = b[blid];
        for(int j = 0; j < m; j++) if(a[j] > b[j] && (a[i] == 0 || a[j] < a[i])){
            mark[j] = true; ty[j] = 1;
            rbl = max(rbl, b[j]);
            //cout << "blue forces " << j << endl;
        }
        for(int j = a[blid]; j != rbl; j = (j + 1) % n)
            have[1][j] = true;
        have[1][rbl] = true;
        solve();
    }

    cout << "impossible" << '\n';

}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13524 KB Output is correct
2 Correct 9 ms 13476 KB Output is correct
3 Incorrect 7 ms 13524 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 8 ms 13524 KB Output is correct
2 Correct 9 ms 13476 KB Output is correct
3 Incorrect 7 ms 13524 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 8 ms 13524 KB Output is correct
2 Correct 9 ms 13476 KB Output is correct
3 Incorrect 7 ms 13524 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 28 ms 16360 KB Output is correct
2 Correct 10 ms 13524 KB Output is correct
3 Correct 15 ms 13012 KB Output is correct
4 Correct 21 ms 16376 KB Output is correct
5 Correct 38 ms 17824 KB Output is correct
6 Correct 33 ms 17692 KB Output is correct
7 Correct 37 ms 17956 KB Output is correct
8 Correct 9 ms 13652 KB Output is correct
9 Correct 9 ms 13524 KB Output is correct
10 Correct 37 ms 17996 KB Output is correct
11 Correct 31 ms 17088 KB Output is correct
12 Correct 37 ms 18176 KB Output is correct
13 Correct 9 ms 13524 KB Output is correct
14 Correct 9 ms 13480 KB Output is correct
15 Correct 36 ms 17356 KB Output is correct
16 Correct 20 ms 16432 KB Output is correct
17 Correct 35 ms 17864 KB Output is correct
18 Correct 32 ms 16712 KB Output is correct
19 Correct 8 ms 12216 KB Output is correct
20 Correct 29 ms 17204 KB Output is correct

Subtask #5
0 / 26.0

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