Submission #441753

#	Time	Username	Problem	Language	Result	Execution time	Memory
441753		abc864197532	Alternating Current (BOI18_alternating)	C++17	100 / 100	347 ms	36056 KiB

alternating

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define test(args...) abc("[" + string(#args) + "]", args)
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
const int mod = 1e9 + 7, N = 100000;
 
vector <int> ans, adj[N];
 
struct Seg {
    int l, r, m;
    vector <int> unknown;
    int one = 0, zero = 0;
    Seg* ch[2];
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m);
            ch[1] = new Seg(m, r);
        }
    }
    void add(int a, int b, int id, int x) {
        if (a <= l && r <= b) {
            if (x == -1) unknown.pb(id);
            if (x == 0) zero++;
            if (x == 1) one++;
        } else {
            if (a < m) ch[0]->add(a, b, id, x);
            if (m < b) ch[1]->add(a, b, id, x);
        }
    }
    int query(int p) {
        if (r - l == 1) return unknown.size();
        return ch[p >= m]->query(p) + unknown.size();
    }
    vector <int> get(int p) {
        if (r - l == 1) return unknown;
        vector <int> a = unknown, b = ch[p >= m]->get(p);
        for (int i : b) a.pb(i);
        return a;
    }
    int val() {return (zero ? 1 : 0) + (one ? 2 : 0);}
    int get2(int p) {
        if (r - l == 1) return val();
        return val() | ch[p >= m]->get2(p);
    }
    int get_unknown(int p) {
        while (!unknown.empty()) {
            int v = unknown.back(); unknown.pop_back();
            if (ans[v] == -1) return v;
        }
        return ch[p >= m]->get_unknown(p);
    }
};
 
int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <pii> a(m);
    Seg root(0, n);
    for (int i = 0, l, r; i < m; ++i) {
        cin >> a[i].X >> a[i].Y, --a[i].X;
        tie(l, r) = a[i];
        if (l < r) {
            root.add(l, r, i, -1);
        } else {
            root.add(l, n, i, -1);
            root.add(0, r, i, -1);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (root.query(i) < 2) return cout << "impossible\n", 0;
        if (root.query(i) == 2) {
            vector <int> tmp = root.get(i);
            adj[tmp[0]].pb(tmp[1]), adj[tmp[1]].pb(tmp[0]);
        }
    }
    auto chg = [&](int i, int x) {
        ans[i] = x;
        int l, r;
        tie(l, r) = a[i];
        if (l < r) {
            root.add(l, r, i, x);
        } else {
            root.add(l, n, i, x);
            root.add(0, r, i, x);
        }
    };
    ans.assign(m, -1);
    bool odd_cycle = false;
    function<void(int)> dfs = [&](int v) {
        for (int u : adj[v]) {
            if (ans[u] == -1) {
                chg(u, ans[v] ^ 1);
                dfs(u);
            } else if (ans[v] == ans[u]) {
                odd_cycle = true;
            }
        }
    };
    for (int i = 0; i < m; ++i) if (ans[i] == -1 && !adj[i].empty()) {
        chg(i, 0);
        dfs(i);
    }
    if (odd_cycle) return cout << "impossible\n", 0;
    vector <int> pp(n);
    iota(all(pp), 0);
    random_shuffle(all(pp));
    for (int i : pp) {
        int ok = root.get2(i);
        if (~ok & 1) {
            int p = root.get_unknown(i);
            chg(p, 0);
        }
        if (~ok & 2) {
            int p = root.get_unknown(i);
            chg(p, 1);
        }
    }
    for (int i : ans) {
        cout << (i == -1 ? 0 : i);
    }
    cout << endl;
}

Compilation message (stderr)

alternating.cpp: In constructor 'Seg::Seg(int, int)':
alternating.cpp:29:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1) {
      |                                            ~~^~~

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