Submission #1259704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259704		inkvizytor	Alternating Current (BOI18_alternating)	C++20	0 / 100	19 ms	9724 KiB

alternating

#include <bits/stdc++.h>
using namespace std;

#define ll long long

vector<int> wyjmij(deque<int> &q, vector<bool> &odw) {
    vector<int> w;
    while (!q.empty() && w.size()<3) {
        if (!odw[q.front()]) {
            q.pop_front();
        }
        w.push_back(q.front());
        q.pop_front();
    }
    for (int i = w.size()-1; i >= 0; i--) {
        q.push_front(w[i]);
    }
    return w;
}

void pchnij(int v, vector<int> &o, vector<int> &x) {
    if (o[v] != o[o[v]]) {
        pchnij(o[v], o, x);
        x[v] ^= x[o[v]];
        o[v] = o[o[v]];
    }
}

void lacz(int a, int b, vector<int> &o, vector<int> &r, vector<int> &x) {
    pchnij(a, o, x);
    pchnij(b, o, x);
    int c = o[a], d = o[b];
    if (c==d) {
        return;
    }
    if (r[c] < r[d]) {
        swap(c, d);
    }
    r[c] += r[d];
    o[d] = c;
    x[d] = x[a]^x[b]^1;
}

bool czy(int a, int b, vector<int> &o, vector<int> &x) {
    pchnij(a, o, x);
    pchnij(b, o, x);
    return o[a] == o[b];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> z (m+1);
    for (int i = 1; i <= m; i++) {
        cin >> z[i].first >> z[i].second;
    }
    vector<vector<int>> v (n);
    for (int i = 1; i <= m; i++) {
        v[z[i].first-1].push_back(i);
        v[z[i].second%n].push_back(-i);
        if (z[i].first > z[i].second) {
            v[0].push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        sort(v[i].begin(), v[i].end());
    }
    vector<bool> odw (m+1, 0);
    deque<int> q;
    vector<vector<int>> k;
    int l = 0;
    for (int i = 0; i < n; i++) {
        bool b = 0;
        for (int j : v[i]) {
            if (j < 0) {
                b = 1;
                if (odw[-j] == 1) {
                    l--;
                }
                odw[-j] = 0;
            }
            else {
                if (odw[j] == 0) {
                    l++;
                }
                odw[j] = 1;
                q.push_back(j);
            }
            
        }
        if (l < 2) {
            cout << "impossible\n";
            return 0;
        }
        if (b) {
            k.push_back(wyjmij(q, odw));
        }
    }
    vector<int> o (m+1, 0), r (m+1, 1), x (m+1, 0);
    for (int i = 0; i <= m; i++) {
        o[i] = i;
    }
    for (auto a : k) {
        if (a.size() == 2) {
            if (czy(a[0], a[1], o, x)) {
                if (x[a[0]]^x[a[1]]^1) {
                    cout << "impossible\n";
                    return 0;
                }
            }
            else {
                lacz(a[0], a[1], o, r, x);
            }
        }
    }
    for (auto a : k) {
        if (a.size() == 3) {
            pchnij(a[0], o, x);
            pchnij(a[1], o, x);
            pchnij(a[2], o, x);
            if (((o[a[0]] == o[a[1]]) && (x[a[0]]^x[a[1]])) || (o[a[0]] != o[a[1]])) {
                lacz(a[0], a[1], o, r, x);
            }
            else if (((o[a[2]] == o[a[1]]) && (x[a[2]]^x[a[1]])) || (o[a[2]] != o[a[1]])) {
                lacz(a[2], a[1], o, r, x);
            }
            else {
                lacz(a[0], a[2], o, r, x);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        pchnij(i, o, x);
        cout << x[i];
    }
    cout << '\n';
}

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