Submission #1259947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259947		inkvizytor	Alternating Current (BOI18_alternating)	C++20	0 / 100	16 ms	7612 KiB

alternating

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

#define ll long long

bool czy(pair<int, int> a, pair<int, int> b) {
    if (a.first > b.first) {
        b.first += 1e9;
        b.second += 1e9;
    }
    if (a.first > a.second) {
        a.second += 1e9;
    }
    if (b.first > b.second) {
        b.second += 1e9;
    }
    return (a.first <= b.first)&&(b.second <= a.second);
}

int sum(int v, int p, int k, vector<int> &tr, int a, int b) {
    if (a <= p && k <= b) {
        return tr[v];
    }
    if (a > k || b < p) {
        return 1e9;
    }
    return min(sum(v*2, p, (p+k)/2, tr, a, b), sum(v*2+1, (p+k)/2+1, k, tr, a, b));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<pair<pair<int, int>, pair<int, int>>> z (m);
    for (int i = 0; i < m; i++) {
        cin >> z[i].second.first >> z[i].second.second;
        if (z[i].second.first > z[i].second.second) {
            z[i].first.first = n-z[i].second.first+1+z[i].second.second;
        }
        else {
            z[i].first.first = z[i].second.second-z[i].second.first+1;
        }
        z[i].first.second = i+1;
    }
    vector<vector<int>> v (n+2);
    for (int i = 0; i < m; i++) {
        v[z[i].second.first].push_back(z[i].first.second);
        v[z[i].second.second+1].push_back(-z[i].first.second);
        if (z[i].second.second < z[i].second.first) {
            v[1].push_back(z[i].first.second);
        }
    }
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end());
    }
    int l = 0;
    vector<int> suma (n+1, 0);
    vector<bool> odw (m+1);
    for (int i = 1; i <= n; i++) {
        for (int j : v[i]) {
            if (j < 0) {
                if (odw[-j]) {
                    l--;
                    odw[-j] = 0;
                }
            }
            else {
                if (!odw[j]) {
                    l++;
                    odw[j] = 1;
                }
            }
        }
        suma[i] = l;
        if (l < 2) {
            cout << "impossible\n";
            return 0;
        }
    }
    sort(z.begin(), z.end(), greater<pair<pair<int, int>, pair<int, int>>>());
    set<pair<pair<int, int>, int>, greater<pair<pair<int, int>, int>>> s;
    vector<int> o (m+1, 0);
    for (int i = 0; i < m; i++) {
        if (s.empty()) {
            o[z[i].first.second] = -1;
            s.insert({z[i].second, z[i].first.second});
            continue;
        }
        auto x = s.lower_bound({{z[i].second.first, (int)1e9}, (int)1e9});
        if (x == s.end()) {
            x--;
        }
        if (czy((*x).first, z[i].second)) {
            o[z[i].first.second] = (*x).second;
        }
        else {
            o[z[i].first.second] = -1;
            s.insert({z[i].second, z[i].first.second});
        }
    }
    vector<int> tr (1<<18, 1e9);
    for (int i = 1; i <= n; i++) {
        tr[i+(1<<17)] = suma[i];
    }
    for (int i = (1<<17)-1; i > 0; i--) {
        tr[i] = min(tr[i*2], tr[i*2+1]);
    }
    vector<pair<pair<int, int>, int>> f;
    for (auto x : s) {
        f.push_back(x);
    }
    reverse(f.begin(), f.end());
    if (!(f.size()%2)) {
        vector<int> w (m+1, 0);
        for (int i = 0; i < (int)f.size(); i++) {
            w[f[i].second] = i%2;
        }
        for (int i = 1; i <= m; i++) {
            if (o[i] != -1) {
                w[i] = w[o[i]]^1;
            }
        }
        for (int i = 1; i <= m; i++) {
            cout << w[i];
        }
        cout << '\n';
        return 0;
    }
    int g = -1;
    for (int i = 0; i < (int)f.size(); i++) {
        int j = (i+1)%(f.size());
        if ((!czy(f[i].first, {f[j].first.first, f[j].first.first})) && (!czy(f[j].first, {f[i].first.second, f[i].first.second}))) {
            g = i;
            break;
        }
        int b = f[j].first.first, e = f[i].first.second;
        int x;
        if (b > e) {
            x = min(sum(1, 0, (1<<17)-1, tr, b, n+1), sum(1, 0, (1<<17)-1, tr, 0, e));
        }
        else {
            x = sum(1, 0, (1<<17)-1, tr, b, e);
        }        
        if (x >= 3) {
            g = i;
            break;
        }
    }
    if (g == -1) {
        cout << "impossible\n";
        return 0;
    }
    vector<int> w (m+1, 0);
    for (int i = 0; i <= g; i++) {
        w[f[i].second] = i%2;
    }
    for (int i = g+1; i < (int)f.size(); i++) {
        w[f[i].second] = (i%2)^1;
    }
    for (int i = 1; i <= m; i++) {
        if (o[i] != -1) {
            w[i] = w[o[i]]^1;
        }
    }
    for (int i = 1; i <= m; i++) {
        cout << w[i];
    }
    cout << '\n';
} 

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