Submission #676919

#	Time	Username	Problem	Language	Result	Execution time	Memory
676919		dooompy	Alternating Current (BOI18_alternating)	C++17	100 / 100	128 ms	23916 KiB

alternating

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

struct wire {
    int l, r, len, idx;
};

vector<wire> wires;
const int MAXT = 555555;

struct bit {
    pair<int, int> tree[MAXT];

    void init() {
        fill(tree, tree+MAXT, pair<int, int> {0, 0});
    }

    void upd(int x, pair<int, int> v) {
        for (; x < MAXT; x += x & (-x)) tree[x] = max(tree[x], v);
    }

    pair<int, int> query(int x) {
        pair<int, int> res = {0, 0};

        for (; x; x -= x & (-x)) {
            res = max(res, tree[x]);
        }

        return res;
    }
} bt;

struct segtree {
    int tree[MAXT];
    int lazy[MAXT];

    void init() {
        fill(tree, tree+MAXT, 0);
        fill(lazy, lazy+MAXT, 0);
    }

    void pushdown(int x, int l, int r) {
        if (l == r) return;

        int mid = (l + r) / 2;

        tree[2 * x] += lazy[x];
        tree[2 * x + 1] += lazy[x];
        lazy[2 * x] += lazy[x];
        lazy[2 * x + 1] += lazy[x];

        lazy[x] = 0;
        return;
    }

    void update(int x, int l, int r, int ql, int qr, int v) {
        pushdown(x, l, r);
        if (ql <= l && r <= qr) {
            lazy[x] += v;
            tree[x] += v;
            return;
        }

        if (l > qr || ql > r) return;

        int mid = (l + r) / 2;

        update(2 * x, l, mid, ql, qr, v);
        update(2* x + 1, mid + 1, r, ql, qr, v);

        tree[x] = min(tree[ 2 * x], tree[2 * x + 1]);
    }

} segs[2];

int par[200005];
vector<int> adj[200005];
int col[200005];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m; cin >> n >> m;

    bt.init();

    segs[0].init(); segs[1].init();

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        if (b < a) {
            wires.push_back({a, b, b + (n - a) + 1, i});
        } else wires.push_back({a, b, b - a + 1, i});
    }

    sort(wires.begin(), wires.end(), [](wire a, wire b) {
        return a.len < b.len;
    });

    vector<wire> doms;

    for (int i = m - 1; i >= 0; i--) {
        int st = wires[i].l, en = wires[i].r;
        if (en < st) en += n;

        auto q = bt.query(st);

        int dom = -1;

        if (q.first >= en) {
            dom = q.second;
        }

        if (dom == -1 && wires[i].l <= wires[i].r) {
            q = bt.query(wires[i].l + n);

            if (q.first >= wires[i].r + n) {
                dom = q.second;
            }
        }

        par[wires[i].idx] = dom;
        if (dom != -1) {
            adj[dom].push_back(wires[i].idx);
        }
        if (par[wires[i].idx] == -1) {
            doms.push_back(wires[i]);

            bt.upd(st, {en, wires[i].idx});

            if (wires[i].l <= wires[i].r) {
                bt.upd(st + n, {en + n, wires[i].idx});
            }
        }
    }

    sort(doms.begin(), doms.end(), [](wire a, wire b) {
        return a.l < b.l;
    });

    sort(wires.begin(), wires.end(), [](wire a, wire b) {
        return a.idx < b.idx;
    });

//    cout << segs[0].query(1, 1, n, 1, n) << endl;


    auto upd = [&](int idx, int v) {
        if (wires[idx].l <= wires[idx].r) {
            segs[col[idx] - 1].update(1, 1, n, wires[idx].l, wires[idx].r, v);
        } else {
            segs[col[idx] - 1].update(1, 1, n, 1, wires[idx].r, v);
            segs[col[idx] - 1].update(1, 1, n, wires[idx].l, n, v);
        }
    };

    int ct = 0;

    for (int i = 0; i < doms.size(); i++) {
        col[doms[i].idx] = 1 + (i % 2);
    }

    for (int i = 0; i < m; i++) {
        if (par[i] != -1) {
            col[i] = 3 - col[par[i]];
        }
    }

    for (int i = 0; i < m; i++) {
        upd(i, 1);
    }

    if (segs[0].tree[1] > 0 && segs[1].tree[1] > 0) {
        for (int i = 0; i < m; i++) {
            cout << col[i] - 1;
        }
        return 0;
    }

    if (doms.size() % 2 == 0 || doms.size() <= 1) {
        cout << "impossible";
        return 0;
    }

    for (int i = 0; i < doms.size(); i++) {
        upd(doms[i].idx, -1);
        col[doms[i].idx] = 3 - col[doms[i].idx];
        upd(doms[i].idx, 1);
        for (auto nxt : adj[doms[i].idx]) {
            upd(nxt, -1);
            col[nxt] = 3 - col[nxt];
            upd(nxt, 1);
        }

        if (segs[0].tree[1] > 0 && segs[1].tree[1] > 0) {
            for (int i = 0; i < m; i++) {
                cout << col[i] - 1;
            }
            return 0;
        }
    }

    cout << "impossible";
}

Compilation message (stderr)

alternating.cpp: In member function 'void segtree::pushdown(int, int, int)':
alternating.cpp:73:13: warning: unused variable 'mid' [-Wunused-variable]
   73 |         int mid = (l + r) / 2;
      |             ^~~
alternating.cpp: In function 'int main()':
alternating.cpp:189:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |     for (int i = 0; i < doms.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
alternating.cpp:215:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<wire>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |     for (int i = 0; i < doms.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
alternating.cpp:187:9: warning: unused variable 'ct' [-Wunused-variable]
  187 |     int ct = 0;
      |         ^~

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