oj.uz

Submission #562182

# Submission time Handle Problem Language Result Execution time Memory
562182 2022-05-14T06:57:43 Z qwerasdfzxcl Alternating Current (BOI18_alternating) C++14
0 / 100
 36 ms 5896 KB 
#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(){
    printf("impossible\n");
    exit(0);
}

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();

        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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Incorrect 2 ms 2644 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Incorrect 2 ms 2644 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Incorrect 2 ms 2644 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5896 KB Output is correct
2 Incorrect 3 ms 3796 KB 'impossible' claimed, but there is a solution
3 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Incorrect 2 ms 2644 KB 'impossible' claimed, but there is a solution
5 Halted 0 ms 0 KB -