Submission #719603

#	Time	Username	Problem	Language	Result	Execution time	Memory
719603		keta_tsimakuridze	Alternating Current (BOI18_alternating)	C++14	0 / 100	173 ms	9288 KiB

alternating

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define Pii pair<pair<int, int>, int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
int n, from[N], last2[N], last3[N];
set<Pii> S;
struct seg{
    int a, b, id;
} p[N];

int try_(seg s) {
    queue<int> q;
    q.push(s.id);
    from[s.id] = 0;
    while(q.size()) {
        int u = q.front();
        q.pop();
        if(p[u].b == n) return u;
        if(p[u].b > n && (s.a > p[u].b || last3[p[u].b] < s.a) && last2[p[u].b] == 0) return u;
        if (p[u].b >= n) continue;
        while (S.upper_bound({{p[u].b + 2, 0}, 0}) != S.begin()) {
            Pii x = *--S.upper_bound({{p[u].b + 2, 0}, 0});
            if (last2[p[u].b] < x.f.f) q.push(x.s), from[x.s] = u, S.erase(x);
            else break;
        }
    }
    return -1;
}
bool cmp(seg a, seg b) {
    return (a.a < b.a);
}
int len(int a, int b) {
    return (b >= a ? b - a + 1 : n - a + 1 + b);
}
int get(int x, int a) {
    if(x >= a) return x - a + 1;

    return n - a + 1 + x;
}
signed main() {
    int m;
    cin >> n >> m;
    int mx = 0;
    for(int i = 1; i <= m; i++) {
        cin >> p[i].a >> p[i].b;
        p[i].id = i;
        if(len(p[i].a, p[i].b) > len(p[mx].a, p[mx].b)) mx = i;
    }
    mx = 1;
    int st = p[mx].a;
    vector<int> c(n + 5);
    for(int i = 1; i <= m; i++) {
        p[i].a = get(p[i].a, st);
        p[i].b = get(p[i].b, st);
        ++c[p[i].a], --c[p[i].b + 1];
        if(p[i].a > p[i].b) ++c[1];
    }

    for(int i = 1; i <= n; i++) {
        c[i] += c[i - 1];
        last3[i] = last3[i - 1];
        last2[i] = last2[i - 1];
        if(c[i] == 1) {
            cout << "impossible";
            return 0;
        }
        if(c[i] == 2) last2[i] = i;
        if(c[i] <= 3) last3[i] = i;
    }
    vector<seg> x;
    for(int i = 1; i <= m; i++) {
        if(i == mx) continue;
        if(p[i].a <= p[mx].b + 1) {
            if(last2[p[mx].b] < p[i].a) x.push_back(p[i]);
        }
        else S.insert({{p[i].a, (p[i].a < p[i].b ? p[i].b : p[i].b + n)}, i});
    }
    sort(x.begin(), x.end(), cmp);
    int ST = (p[mx].b == n ? mx : -1);
    while(x.size()) {

        seg s = x.back(); x.pop_back();

        ST = try_(s);
        if(ST != -1) {
            ST = s.id;
            break;
        }
    }
    if(ST == -1) {
        cout << "impossible";
        return 0;
    }
    S.clear();
    for(int i = 1; i <= m; i++) {
        if(i == mx) continue;
        if(p[i].a <= p[mx].b + 1) {}
        else S.insert({{p[i].a, (p[i].a < p[i].b ? p[i].b : p[i].b + n)}, i});
    }
    vector<int> ans(m + 5); ans[mx] = 1;
    int EN = try_(p[ST]);
  	if(EN == -1) {
      while(true) EN = -1;
    }
    while(EN) {
        ans[EN] = 1;
        EN = from[EN];
    }
    for(int i = 1; i <= m; i++) cout << ans[i] << "";
}
/*
 10 5
 1 5
 6 7
 5 1
 7 2
 2 4
 */

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