oj.uz

Submission #1115062

# Submission time Handle Problem Language Result Execution time Memory
1115062 2024-11-19T23:43:59 Z lucascgar Alternating Current (BOI18_alternating) C++17
19 / 100
 89 ms 10824 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
/*
 
*/
 
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
 
const int MAXN = 1e5+10;
 
vector<int> w[MAXN];
bool ty[MAXN];

pii cb[MAXN];
int act[MAXN][2];
bool us[MAXN];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout << fixed << setprecision(7);
 
    int n, m;
    cin >> n >> m;
 
    int a, b;
    vector<int> cy;
    for (int i=0;i<m;i++){
        cin >> a >> b;
        cb[i] = {a,b};
        if(b<a){
            if (b==a-1){
                a=1,b=n;
            }else{
                cy.push_back(i);
                continue;
            }
        }
        w[a].push_back(i);
        w[b].push_back(i);
    }
    set<int> cr;

    act[1][0] = act[1][1]=-1;

    for (int i=1;i<=n;i++){
        vector<int> rm;
        while (!w[i].empty()){
            int u = w[i].back();
            w[i].pop_back();
            if (cr.count(u) || act[i][0] == u || act[i][1]==u){
                rm.push_back(u);
            }else{
                cr.insert(u);
            }
        }
 
        if (act[i][0]==-1 && !cr.empty()){
            act[i][0] = *cr.begin();
            cr.erase(cr.begin());
            ty[act[i][0]]=0;
        }
        if (act[i][1]==-1 && !cr.empty()){
            act[i][1] = *cr.begin();
            cr.erase(cr.begin());
            ty[act[i][1]]=1;
        }

        act[i+1][0]=act[i][0], act[i+1][1]=act[i][1];
        for (auto &u:rm){
            cr.erase(u);
            if (act[i][0]==u) act[i+1][0]=-1;
            if (act[i][1]==u) act[i+1][1]=-1;
        }
    }

    for (auto &x:cy){
        a=cb[x].first, b = cb[x].second;
        w[a].push_back(x);
    }

    set<pii> ac; // {esquerda, cara}
    int has[2] = {-1,-1};
    for (int i=1;i<=n;i++){
        while (!w[i].empty()){
            int u = w[i].back();
            w[i].pop_back();
            ac.emplace(cb[u].second, u);
        }

        for (int j=0;j<2;j++) if (has[j]!=-1) act[i][j]=has[j];

        for (int j=0;j<2;j++){
            if (act[i][j]==-1 && !ac.empty()){
                int u = ac.begin()->second;
                ac.erase(ac.begin());
                us[u] = 1, ty[u]=j, has[j]=act[i][j]=u;
            }
        }

    }


    cr.clear();
    set<int> st[2], sc;
    for (auto &x:cy){
        w[cb[x].second].push_back(x);
        if (us[x]) st[ty[x]].insert(x);
        else sc.insert(x);
    }

    for (int i=1;i<=n;i++){
        vector<int> rm;
        while (!w[i].empty()){
            rm.push_back(w[i].back());
            w[i].pop_back();
        }

        bool valid = 1;
        for (int j=0;j<2;j++){
            if (act[i][j]==-1 && st[j].empty()){

                if (sc.empty()){
                    valid = 0;
                    break;
                }

                int u = *sc.begin();
                sc.erase(sc.begin());
                us[u]=1, ty[u]=j;
                st[j].insert(u);

            }
        }

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

        for (auto &u:rm){
            st[0].erase(u);
            st[1].erase(u);
            sc.erase(u);
        }
    }
 
    for (int i=0;i<m;i++) cout << (int)ty[i];
    cout << '\n';
 
    return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 22.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 10684 KB Output is correct
2 Correct 3 ms 4432 KB Output is correct
3 Correct 28 ms 10312 KB Output is correct
4 Correct 33 ms 10320 KB Output is correct
5 Correct 35 ms 8008 KB Output is correct
6 Correct 39 ms 7752 KB Output is correct
7 Correct 33 ms 8268 KB Output is correct
8 Correct 5 ms 4432 KB Output is correct
9 Correct 4 ms 4432 KB Output is correct
10 Correct 45 ms 8264 KB Output is correct
11 Correct 31 ms 8028 KB Output is correct
12 Correct 37 ms 8284 KB Output is correct
13 Correct 3 ms 4432 KB Output is correct
14 Correct 3 ms 4432 KB Output is correct
15 Correct 33 ms 7660 KB Output is correct
16 Correct 30 ms 10312 KB Output is correct
17 Correct 89 ms 10824 KB Output is correct
18 Correct 81 ms 8868 KB Output is correct
19 Correct 6 ms 4932 KB Output is correct
20 Correct 24 ms 7256 KB Output is correct

Subtask #5
0 / 26.0

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