Submission #562211

#	Time	Username	Problem	Language	Result	Execution time	Memory
562211		qwerasdfzxcl	Alternating Current (BOI18_alternating)	C++14	0 / 100	26 ms	4772 KiB

alternating

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Wire{
    int s, e;
    Wire(){}
    Wire(int _s, int _e): s(_s), e(_e) {}
}a[100100];
int cnt[100100], b[200200], validS[100100], ans[100100];
vector<int> V[100100];

int find_valid(int l, int r){
    if (l>r) return r+1;
    int ret = r+1, rr = r;
    while(l<=r){
        int m = (l+r)>>1;
        if (validS[rr] - validS[m-1] == rr - m + 1) ret = m, r = m-1;
        else l = m+1;
    }
    return ret;
}

void no(int ret = 0){
    printf("impossible\n");
    exit(ret);
}

int main(){
    int n, m, len = 0, idx = -1;
    scanf("%d %d", &n, &m);

    for (int i=1;i<=m;i++){
        scanf("%d %d", &a[i].s, &a[i].e);
        if (a[i].e < a[i].s) a[i].e += n;

        if (len < a[i].e - a[i].s + 1){
            len = a[i].e - a[i].s + 1;
            idx = i;
        }
    }

    int val = 1;
    //printf("%d %d %d\n", len, idx, val);
    for (int i=1;i<=m;i++){
        a[i].s -= val-1, a[i].e -= val-1;
        if (a[i].s<=0) a[i].s += n, a[i].e += n;

        V[a[i].s].push_back(i);
        b[a[i].s] += 1;
        b[a[i].e+1] -= 1;
    }

    for (int i=1;i<=n*2;i++){
        cnt[i] = cnt[i-1] + b[i];
        //printf("%d ", cnt[i]);
    }
    //printf("\n");
    for (int i=1;i<=n;i++){
        cnt[i] += cnt[i+n];
        validS[i] = validS[i-1];
        if (cnt[i]>=3) validS[i]++;
        if (cnt[i]<=1) no();
    }

    int prv = 0, cur = 0;

    while(true){
        int L = find_valid(prv+1, cur);
        int R = 0;
        idx = -1;
        for (int i=L;i<=cur+1;i++){
            for (auto &j:V[i]) if (R < a[j].e){
                R = a[j].e;
                idx = j;
            }
        }
        //printf("%d %d %d %d %d\n", prv, cur, L, R, idx);
        if (idx==-1) no(2);

        ans[idx] = 1;
        if (R>=n) break;
        prv = cur+1;
        cur = R;
    }

    for (int i=1;i<=m;i++) printf("%d", ans[i]);
    return 0;
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
alternating.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%d %d", &a[i].s, &a[i].e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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