Submission #1260527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260527		niepamietamhasla	Alternating Current (BOI18_alternating)	C++20	0 / 100	26 ms	9392 KiB

alternating

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;

const int MAXN = 1e5 + 5;

struct d{
    int a;
    int b;
    int nr;
};

int ans[MAXN];

vector<d> dzieci[MAXN];
int P[MAXN];

vector<d> przedzialy;

bool comp(const d &d1, const d &d2){
    if(d1.a != d2.a) return d1.a < d2.a;
    return false;
}

vector<d> wejscie;

int pref[MAXN][2];

int G[MAXN];
int G2[MAXN];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    cout << n << " " << m << "\n";
    int a, b;
    for(int i = 1; i <= m; ++i){
        cin >> a >> b;
        cout << a << " " << b << "\n";
        wejscie.push_back({a, b, i});
        if(a > b){
            G[a]++;
            G[1]++;
            G[b+1]--;
        }
        else{
            G[a]++;
            G[b+1]--;
        }
        if(a > b) b += n;
        przedzialy.push_back({a, b, i});
    }
    for(int i = 1; i <= n; ++i){
        G[i] += G[i-1];
        if(G[i] <= 1){
            cout << "impossible\n";
            return 0;
        }
    }
    sort(przedzialy.begin(), przedzialy.end(), comp);
    int ma = 0;
    int ind = -1;
    for(auto u : przedzialy){
        if(ma >= u.b){
            P[u.nr] = ind;
            dzieci[ind].push_back(u);
        }
        else{
            ma = u.b;
            ind = u.nr;
        }
    }
    przedzialy.clear();
    for(int i = 1; i <= m; ++i){
        if(P[i] != 0){
        }
        else{
            przedzialy.push_back(wejscie[i-1]);
        }
    }

    sort(przedzialy.begin(), przedzialy.end(), comp);
    // for(auto u : przedzialy){
    //     cout << u.a << " " << u.b << " U\n";
    // }
    if(przedzialy.size() % 2 == 0){
        for(int i = 0; i < przedzialy.size(); ++i){
            int ktory = (i % 2);
            if(przedzialy[i].a > przedzialy[i].b){
                pref[przedzialy[i].a][ktory]++;
                pref[1][ktory]++;
                pref[przedzialy[i].b+1][ktory]--;
            }
            else{
                pref[przedzialy[i].a][ktory]++;
                pref[przedzialy[i].b+1][ktory]--;
            }
            ans[przedzialy[i].nr] = ktory;
            ktory ^= 1;
            for(auto u : dzieci[przedzialy[i].nr]){
                if(u.a > u.b){
                    pref[u.a][ktory]++;
                    pref[1][ktory]++;
                    pref[u.b+1][ktory]--;
                }
                else{
                    pref[u.a][ktory]++;
                    pref[u.b+1][ktory]--;
                }
                ans[u.nr] = ktory;
            }
        }   
        bool c = true;
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j < 2; ++j){
                pref[i][j] += pref[i-1][j];
                if(pref[i][j] <= 0) c = false;
            }
        }
        if(c){
            for(int i = 1; i <= m; ++i){
                cout << ans[i];
            }
            cout << "\n";
        }
        else{
            cout << "impossible\n";
        }
    }
    else{
        if(przedzialy.size() == 1){
            auto u = przedzialy[0];
            int ktory = 0;
            if(u.a > u.b){
                pref[u.a][ktory]++;
                pref[1][ktory]++;
                pref[u.b+1][ktory]--;
            }
            else{
                pref[u.a][ktory]++;
                pref[u.b+1][ktory]--;
            }
            ans[u.nr] = ktory;
            ktory ^= 1;
            for(auto y : dzieci[u.nr]){
                if(y.a > y.b){
                    pref[y.a][ktory]++;
                    pref[1][ktory]++;
                    pref[y.b+1][ktory]--;
                }
                else{
                    pref[y.a][ktory]++;
                    pref[y.b+1][ktory]--;
                }
                ans[y.nr] = ktory;
            }
            bool c = true;
            for(int i = 1; i <= n; ++i){
                for(int j = 0; j < 2; ++j){
                    pref[i][j] += pref[i-1][j];
                    if(pref[i][j] <= 0) c = false;
                }
            }
            if(c){
                for(int i = 1; i <= m; ++i){
                    cout << ans[i];
                }
                cout << "\n";
            }
            else{
                cout << "impossible\n";
            }
            return 0;
        }
        for(int i = 1; i <= n; ++i){
            if(G[i] > 2) G2[i]++;
            G2[i] += G2[i-1];
        }
        int sajz = przedzialy.size();
        for(int i = 0; i < sajz; ++i){
            int nxt = (i == sajz - 1 ? 0 : i+1);
            auto u = przedzialy[i];
            auto v = przedzialy[nxt];
            //cout << u.a << " " << u.b << " U\n";
            auto intersect = [=](d A, d B) -> vector<pii>{
                if(A.a <= A.b and B.a <= B.b){
                    //cout << "#\n";
                    if(A.b >= B.a) return {{B.a, A.b}};
                    else return {};
                }
                else if(A.a > A.b and B.a > B.b){
                    //cout << "$\n";
                    vector<pii> D;
                    D = {{max(A.a, B.a), n}, {1, min(A.b, B.b)}};
                    if(A.b >= B.a){
                        D.push_back({B.a, A.b});
                    }
                    return D;
                }
                else if(A.a <= A.b and B.a > B.b){
                    //cout << "^\n";
                    if(A.b >= B.a and B.b >= A.a){
                        return {{B.a, A.b}, {A.a, B.b}};
                    }
                    else if(A.b >= B.a){
                        return {{B.a, A.b}};
                    }
                    else if(B.b >= A.a){
                        return {{A.a, B.b}};
                    }
                    else{
                        return {};
                    }
                }
                else{
                    //cout << "&\n";
                    swap(A, B);
                    if(A.b >= B.a and B.b >= A.a){
                        return {{B.a, A.b}, {A.a, B.b}};
                    }
                    else if(A.b >= B.a){
                        return {{B.a, A.b}};
                    }
                    else if(B.b >= A.a){
                        return {{A.a, B.b}};
                    }
                    else{
                        return {};
                    }
                }
            };
            vector<pii> C = intersect(u, v);
            // cout << i << " i\n";
            // for(auto u : C){
            //     cout << u.first << " " << u.second << " pr\n";
            // }
            bool c = true;
            for(auto x : C){
                //cout << x.first << " " << x.second << "X\n";
                //cout << G2[x.second] - G2[x.first - 1] << " " << x.second - x.first + 1 << " por\n";
                if(G2[x.second] - G2[x.first - 1] != x.second - x.first + 1){
                    c = false;
                }
            }
            if(c){
                //cout << i << " i\n";
                //cout << "#\n";
                ans[przedzialy[i].nr] = 0;
                ans[przedzialy[nxt].nr] = 0;
                for(auto u : dzieci[przedzialy[i].nr]){
                    ans[u.nr] = ans[przedzialy[i].nr] ^ 1;
                }
                for(auto u : dzieci[przedzialy[nxt].nr]){
                    ans[u.nr] = ans[przedzialy[nxt].nr] ^ 1;
                }
                if(nxt == 0){
                    //cout << "$\n";
                    for(int j = nxt + 1; j < i; ++j){
                        ans[przedzialy[j].nr] = ans[przedzialy[j - 1].nr] ^ 1;
                        for(auto u : dzieci[przedzialy[j].nr]){
                            ans[u.nr] = ans[przedzialy[j].nr] ^ 1;
                        }
                    }
                    for(int j = 1; j <= m; ++j){
                        cout << ans[j];
                    }
                    cout << "\n";
                    return 0;
                }
                else{
                    for(int j = i - 1; j >= 0; --j){
                        ans[przedzialy[j].nr] = ans[przedzialy[j + 1].nr] ^ 1;
                        for(auto u : dzieci[przedzialy[j].nr]){
                            ans[u.nr] = ans[przedzialy[j].nr] ^ 1;
                        }
                    }
                    for(int j = nxt + 1; j < sajz; ++j){
                        ans[przedzialy[j].nr] = ans[przedzialy[j - 1].nr] ^ 1;
                        for(auto u : dzieci[przedzialy[j].nr]){
                            ans[u.nr] = ans[przedzialy[j].nr] ^ 1;
                        }
                    }
                    for(int j = 1; j <= m; ++j){
                        cout << ans[j];
                    }
                    cout << "\n";
                    return 0;
                }           
            }
        }
        cout << "impossible\n";
    }
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26