Submission #1115062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115062		lucascgar	Alternating Current (BOI18_alternating)	C++17	19 / 100	89 ms	10824 KiB

alternating

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26