제출 #1260520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260520		M_W_13	Alternating Current (BOI18_alternating)	C++20	100 / 100	28 ms	11612 KiB

alternating

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
int n, m;
const int MAXN = 2e5 + 7;
bool jaki[MAXN];

struct przedzial {
    int l, r, kt;
};

vector<przedzial> prz;

bool sor(przedzial a, przedzial b) {
    return (a.r < b.r);
}

int zmien(int a, int x) {
    a -= x;
    a += n;
    a %= n;
    return a;
}

struct zmiana {
    int pr0, pr1;
    int kt;
    int po0, po1;
    bool c;
};

bool rob(pair<int, int> uz, pair<int, int> dok, pair<int, int> start) {
    // cout << uz.st << " " << uz.nd << '\n';
    pair<int, int> p0 = start;
    pair<int, int> p1 = start;
    vector<zmiana> zm;
    // cout << "XD " << p0.st << " " << p0.nd << " " << p1.st << " " << p1.nd << '\n';
    rep(i, m) {
        if (prz[i].kt == uz.st || prz[i].kt == uz.nd) {
            continue;
        }
        int l = prz[i].l;
        int r = prz[i].r;
        int nr = prz[i].kt;
        pair<int, int> n0;
        pair<int, int> n1;
        if (l <= p1.st + 1) {
            if (r > p1.st) {
                n0 = {r, p1.nd};
                zm.pb({p1.st, p1.nd, nr, n0.st, n0.nd, 0});
            }
            else {
                n0 = p0;
            }
        }
        else {
            if (l <= p0.st + 1) {
                if (r > p0.st) {
                    n0 = {r, p0.nd};
                    zm.pb({p0.st, p0.nd, nr, n0.st, n0.nd, 0});
                }
                else {
                    n0 = p0;
                }
            }
            else {
                n0 = p0;
            }
        }
        if (l <= p0.nd + 1) {
            if (r > p0.nd) {
                n1 = {p0.st, r};
                // cout << "nr = " << nr << '\n';
                zm.pb({p0.st, p0.nd, nr, n1.st, n1.nd, 1});
            }
            else {
                n1 = p1;
            }
        }
        else {
            if (l <= p1.nd + 1) {
                if (r > p1.nd) {
                    n1 = {p1.st, r};
                    zm.pb({p1.st, p1.nd, nr, n1.st, n1.nd, 1});
                }
                else {
                    n1 = p1;
                }
            }
            else {
                n1 = p1;
            }
        }
        p0 = n0;
        p1 = n1;
        // cout << p0.st << " " << p0.nd << " " << p1.st << " " << p1.nd << '\n';
    }
    if (p1.st >= dok.st && p1.nd >= dok.nd) {
        p0 = p1;
    }
    if (p0.st >= dok.st && p0.nd >= dok.nd) {
        jaki[uz.st] = 0;
        jaki[uz.nd] = 1;
        int roz = zm.size();
        int las = -1;
        for (int i = roz - 1; i >= 0; i--) {
            if (zm[i].po0 == p0.st && zm[i].po1 == p0.nd && zm[i].kt != las) {
                p0 = {zm[i].pr0, zm[i].pr1};
                jaki[zm[i].kt] = zm[i].c;
                las = zm[i].kt;
            }
        }
        return true;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    // cout << n << " " << m << '\n';
    int dlm = 0;
    int kt = 0;
    rep(i, m) {
        int l, r;
        cin >> l >> r;
        // cout << l << " " << r << '\n';
        l--;
        r--;
        prz.pb({l, r, i});
        int d = r - l + 1;
        if (d <= 0) {
            d += n;
        }
        if (d > dlm) {
            dlm = d;
            kt = i;
        }
    }
    przedzial pr = prz[kt];
    int x = pr.l;
    pr.l = zmien(pr.l, x);
    pr.r = zmien(pr.r, x);
    vector<pair<int, int>> jakie;
    rep(i, m) {
        prz[i].l = zmien(prz[i].l, x);
        // cout << "prz = " << prz[i].r << '\n';
        prz[i].r = zmien(prz[i].r, x);
        // cout << " prz2 = " << prz[i].r << '\n';
        if (i == kt) continue;
        if (prz[i].r < prz[i].l || prz[i].l == 0) {
            jakie.pb({prz[i].r, prz[i].kt});
        }
    }
    sort(jakie.begin(), jakie.end());
    reverse(jakie.begin(), jakie.end());
    if ((int)jakie.size() == 0) {
        cout << "impossible" << '\n';
        return 0;
    }
    int sz = jakie.size();
    vector<vector<pair<int, int>>> pyt;
    rep(i, min(2, sz)) {
        // cout << "jakie = " << jakie[i].nd << '\n';
        // cout << prz[kt].r << '\n';
        // cout << prz[jakie[i].nd].l << " " << prz[jakie[i].nd].r << '\n';
        pyt.pb({{kt, jakie[i].nd}, {n - 1, (prz[jakie[i].nd].l - 1 + n) % n}, {prz[kt].r, prz[jakie[i].nd].r}});
    }
    rep(i, m) {
        if (prz[i].r < prz[i].l) {
            prz[i].r = n - 1;
        }
    }
    sort(prz.begin(), prz.end(), sor);
    for (auto que: pyt) {
        // cout << que[2].st << " " << que[2].nd << '\n';
        if (rob(que[0], que[1], que[2])) {
            rep(i, m) {
                cout << jaki[i];
            }
            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