Submission #1260557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260557		niepamietamhasla	Alternating Current (BOI18_alternating)	C++20	100 / 100	49 ms	10940 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 org;
};

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 n, m;
int pref[MAXN][2];

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

bool comp2(const d &d1, const d &d2){
    int s1;
    if(d1.a <= d1.b) s1 = d1.b - d1.a + 1;
    else s1 = n - d1.a + 1 + d1.b;
    int s2;
    if(d2.a <= d2.b) s2 = d2.b - d2.a + 1;
    else s2 = n - d2.a + 1 + d2.b;
    if(s1 != s2){
        return s1 > s2;
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    //cout << n << " " << m << "\n";
    int a, b;
    for(int i = 1; i <= m; ++i){
        ans[i] = -1;
        cin >> a >> b;
        //cout << a << " " << b << "\n";
        if(a > b){
            G[a]++;
            G[1]++;
            G[b+1]--;
        }
        else{
            G[a]++;
            G[b+1]--;
        }
        przedzialy.push_back({a, b, i, 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(), comp2);
    int cnt = 1;
    for(auto &u : przedzialy){
        //cout << u.a << " " << u.b << " LK\n";
        u.nr = cnt;
        cnt++;
    }
    set<pii> duze;
    for(auto u : przedzialy){
        //  cout << u.a << " " << u.b << " " << u.nr << " po kolei\n";
        int p = -1;
        auto it = duze.lower_bound({u.a, 1e9});
        if(it != duze.begin()){
            //cout << it->first << " " << it->second << " curr\n";
            p = (*(--it)).second;
        }
        else{
            if(duze.size() != 0) p = (*(--duze.end())).second;
        }
        //cout << p << " P\n";\
        P[u.nr] = p;
        if(p == -1){
            duze.insert({u.a, u.nr});
        }
        else{   
            if(u.a <= u.b){
                if(przedzialy[p-1].a <= przedzialy[p-1].b){
                    if(!(przedzialy[p-1].a <= u.a and przedzialy[p-1].b >= u.b)) duze.insert({u.a, u.nr});
                    else dzieci[p].push_back(u);
                }
                else{
                    if(!(przedzialy[p-1].a <= u.a or przedzialy[p-1].b >= u.b)) duze.insert({u.a, u.nr});
                    else dzieci[p].push_back(u);
                }
            }
            else{
                if(przedzialy[p-1].a <= przedzialy[p-1].b){
                    duze.insert({u.a, u.nr});
                }
                else{
                    if(!(przedzialy[p-1].a <= u.a and przedzialy[p-1].b >= u.b) and przedzialy[p-1  ].a != (przedzialy[p-1].b+1)%n){
                        duze.insert({u.a, u.nr});
                    }
                    else{
                        dzieci[p].push_back(u);
                    }
                }
            }   
        }
    }   
    vector<d> tmp;
    for(auto u : duze){
        //cout << u.first << " " << u.second << " duze\n";
        tmp.push_back(przedzialy[u.second-1]);
    }
    przedzialy = tmp;
    sort(przedzialy.begin(), przedzialy.end(), comp);
    // for(auto u : przedzialy){
    //     cout << u.a << " " << u.b << " U\n";
    // }
    // return 0;
    
    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].org] = 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.org] = 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.org] = 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.org] = 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].org] = 0;
                ans[przedzialy[nxt].org] = 0;
                for(auto u : dzieci[przedzialy[i].nr]){
                    ans[u.org] = ans[przedzialy[i].org] ^ 1;
                }
                for(auto u : dzieci[przedzialy[nxt].nr]){
                    ans[u.org] = ans[przedzialy[nxt].org] ^ 1;
                }
                if(nxt == 0){
                    //cout << "$\n";
                    for(int j = nxt + 1; j < i; ++j){
                        ans[przedzialy[j].org] = ans[przedzialy[j - 1].org] ^ 1;
                        for(auto u : dzieci[przedzialy[j].nr]){
                            ans[u.org] = ans[przedzialy[j].org] ^ 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].org] = ans[przedzialy[j + 1].org] ^ 1;
                        //cout << przedzialy[j].a << " " << przedzialy[j].b << " ab1\n";
                        for(auto u : dzieci[przedzialy[j].nr]){
                            //cout << u.a << " " << u.b << " syn1\n";
                            ans[u.org] = ans[przedzialy[j].org] ^ 1;
                        }
                    }
                    for(int j = nxt + 1; j < sajz; ++j){
                        ans[przedzialy[j].org] = ans[przedzialy[j - 1].org] ^ 1;
                        //cout << przedzialy[j].a << " " << przedzialy[j].b << " ab2\n";
                        for(auto u : dzieci[przedzialy[j].nr]){
                            //cout << u.a << " " << u.b << " syn2\n";
                            ans[u.org] = ans[przedzialy[j].org] ^ 1;
                        }
                    }
                    for(int j = 1; j <= m; ++j){
                        cout << ans[j];
                    }
                    cout << "\n";
                    return 0;
                }           
            }
        }
        cout << "impossible\n";
    }
    return 0;
}

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