Submission #1259981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259981		patgra	Alternating Current (BOI18_alternating)	C++20	100 / 100	987 ms	13960 KiB

alternating

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto a : (b))
#define repIn2(a, b, c) for(auto [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> v(m);
    rep(i, 0, m) cin >> v[i].first >> v[i].second;
    set<pair<int, int>> outerOnes, s2;
    vector<bool> fillable(n + 1), ans(m);
    vector<pair<int, int>> innerOnes;
    rep(i, 1, n + 1) outerOnes.insert({i, i});
    repIn2(a, b, v) {
        if((a == 1 && b == n) || a == b + 1) {
            outerOnes.clear();
            outerOnes.insert({a, b});
             DC << a << ' ' << b << " instead of everything " << eol;
            break;
        }
        auto it = outerOnes.upper_bound({a, 1e9});
        if(it == outerOnes.begin()) it = outerOnes.end();
        it--;
        auto [l1, r1] = *it;
        if(b < a) b += n;
        if(r1 < l1) r1 += n;
        if(l1 <= a && b <= r1) continue;
        if(l1 <= a + n && b + n <= r1) continue;
         DC << a << ' ' << (b - 1) % n + 1 << " instead of ";
        bool stop = false;
        bool start = true, dupa;
        auto st = l1;
        while(!stop) {
            auto [l, r] = *it;
            if(r < l) r += n;
            dupa = false;
            if((a <= l && r <= b) || (a <= l + n && r + n <= b)) {
                 DC << ' ' << it -> first << ' ' << it -> second << ' ';
                if(next(it) == outerOnes.end() && outerOnes.size() != 1 && it -> first == st) st = outerOnes.begin() -> first, dupa = true;
                if(next(it) != outerOnes.end() && outerOnes.size() != 1 && it -> first == st) st = next(it) -> first, dupa = true;
                outerOnes.erase(prev(++it));
            }
            else it++;
            start = start || dupa;
            if(it == outerOnes.end()) it = outerOnes.begin();
            if(outerOnes.empty()) break;
            auto [l2, r2] = *it;
            if(l2 > b || (l2 < a && l2 + n > b)) stop = true;
            if(l2 == l || (l <= a && l2 >= st && !start) || (l > l2 && l2 + n > b && !start)) stop = true;
            start = dupa;
        }
         DC << eol;
        outerOnes.insert({a, (b - 1) % n + 1});
    }

    DC << "outerOnes: \n";
    repIn2(a, b, v) {
        if(outerOnes.count({a, b})) {
            s2.insert({a, b});
            DC << ' ' << a << ' ' << b << eol;
            outerOnes.erase({a, b});
        }
        else innerOnes.pb({a, b});
    }
    DC << eol;
    swap(s2, outerOnes);
    ranges::sort(innerOnes);
    int whereTo = 0;
    repIn2(a, b, innerOnes) {
        if(b < a) b += n;
        rep(i, max(a, whereTo + 1), max(b + 1, whereTo + 1)) fillable[(i - 1) % n + 1] = true;
        whereTo = max(whereTo, b);
    }
    DC << "fillable: ";
    rep(i, 1, n + 1) DC << fillable[i];
    DC << eol;

    set<pair<pair<int, int>, bool>> outer2;
    if(outerOnes.size() > 1 && outerOnes.size() % 2 == 1) {
        int lastEnd = prev(outerOnes.end()) -> second;
        if(lastEnd == n) lastEnd = 0;
        auto it2 = outerOnes.begin(), it1 = it2++;
        bool works = false;
        while(it2 != outerOnes.end()) {
            works = true;
            int nextStart = (next(it2) == outerOnes.end() ? outerOnes.begin() -> first + n : next(it2) -> first);
            int leftInter = max(lastEnd + 1, it2 -> first);
            int rightInter = min(nextStart - 1, it1 -> second + (it1 -> second < it1 -> first ? n : 0));
            if(it1 -> second + 1 != it2 -> first) {
                if(leftInter > rightInter) break;
                bool g = true;
                rep(i, leftInter, rightInter + 1) g = g && fillable[(i - 1) % n + 1];
                if(g) break;
            }
            else break;
            lastEnd = max(lastEnd, it1 -> second + (it1 -> second < it1 -> first ? n : 0));
            it1++;
            it2++;
            works = false;
        }
        if(!works) {
            it2 = outerOnes.begin();
            int nextStart = next(outerOnes.begin()) -> first + n;
            int leftInter = max(lastEnd + 1, it2 -> first + n);
            int rightInter = min(nextStart - 1, it1 -> second + (it1 -> second < it1 -> first ? n : 0));
            if(it1 -> second + (it1 -> second < it1 -> first ? n : 0) >= it2 -> first + n) {
                if(leftInter > rightInter) works = true;
                bool g = true;
                rep(i, leftInter, rightInter + 1) g = g && fillable[(i - 1) % n + 1];
                if(g) works = true;
            }
            else works = true;
        }
        if(!works) { cout << "impossible\n"; return 0; }
        bool side = 0;
        DC << "same: " << it1 -> first << ' ' << it2 -> first << eol;
        repIn(i, outerOnes) outer2.insert({i, side}), side = (i == *it1 ? side : !side);
    }
    else {
        bool side = 0;
        repIn(i, outerOnes) outer2.insert({i, side}), side = !side;
    }

    rep(i, 0, m) {
        auto [a, b] = v[i];
        auto it = outer2.upper_bound({{a, m + n + 1}, 1});
        if(it == outer2.begin()) it = outer2.end();
        it--;
        if(outerOnes.count({a, b})) {
            ans[i] = it -> second;
            outerOnes.erase({a, b});
            continue;
        }
        ans[i] = !(it -> second);
    }

    vector<pair<int, int>> myHalf;
    vector<bool> reached(n);
    rep(i, 0, m) if(ans[i]) myHalf.pb(v[i]);
    int lastOne = 0;
    ranges::sort(myHalf);
    repIn2(a, b, myHalf) {
        if(b < a) b += n;
        rep(i, max(lastOne + 1, a), max(lastOne + 1, b + 1)) reached[(i - 1) % n] = true;
        lastOne = max(lastOne, b);
    }
    bool g = true;
    rep(i, 0, n) g = g && reached[i];
    myHalf.clear();
    rep(i, 0, m) if(!ans[i]) myHalf.pb(v[i]);
    lastOne = 0;
    ranges::sort(myHalf);
    repIn2(a, b, myHalf) {
        if(b < a) b += n;
        rep(i, max(lastOne + 1, a), max(lastOne + 1, b + 1)) reached[(i - 1) % n] = false;
        lastOne = max(lastOne, b);
    }
    rep(i, 0, n) g = g && !reached[i];
    if(!g) { cout << "impossible\n"; return 0; }

    rep(i, 0, m) cout << ans[i];
    cout << '\n';
}

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