oj.uz

Submission #941307

# Submission time Handle Problem Language Result Execution time Memory
941307 2024-03-08T13:25:22 Z phoenix0423 Alternating Current (BOI18_alternating) C++17
0 / 100
 63 ms 14864 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e18;
int n, m;

struct seg{
    int l, r, id;
    seg(){}
    seg(int _l, int _r, int _id) : l(_l), r(_r), id(_id){
        if(r < l) r += n;
    }
    bool operator < (const seg& other) const{
        if(l != other.l) return l < other.l;
        return r < other.r;
    }
};

class comp{
    public:
        bool operator ()(seg a, seg b){
            if(a.r != b.r) return a.r < b.r;
            else return a.l < b.l;
        }
};

int st[maxn * 4], tag[maxn * 4];

void cast(int val, int v){
    st[v] += val, tag[v] += val;
}

void push(int v){
    if(tag[v]){
        cast(tag[v], v * 2);
        cast(tag[v], v * 2 + 1);
        tag[v] = 0;
    }
}
void upd(int l, int r, int val, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return;
    if(l <= L && r >= R){
        st[v] += val, tag[v] += val;
        return;
    }
    push(v);
    int m = (L + R) / 2;
    upd(l, r, val, v * 2, L, m);
    upd(l, r, val, v * 2 + 1, m + 1, R);
    st[v] = min(st[v * 2], st[v * 2 + 1]);
}
int qry(int l, int r, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return INF;
    if(l <= L && r >= R) return st[v];
    push(v);
    int m = (L + R) / 2;
    return min(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}
void insert(int l, int r, int val){
    l %= n, r %= n;
    if(l <= r) upd(l, r, val);
    else upd(l, n - 1, val), upd(0, r, val);
}

bool ck(seg a){
    a.l %= n, a.r %= n;
    if(a.l <= a.r) return qry(a.l, a.r) >= 2;
    else return min(qry(a.l, n - 1), qry(0, a.r)) >= 2;
}
int getlen(int a, int b){
    return (b - a + n) % n + 1;
}
signed main(void){
    fastio;
    cin>>n>>m;
    vector<seg> e;
    int mx = -INF;
    int st = 0;
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        if(getlen(a, b) > mx) mx = getlen(a, b), st = a;
        insert(a, b, 1);
        e.pb(seg(a, b, i));
    }
    if(qry(0, n - 1) < 2){
        cout<<"impossible\n";
        return 0;
    }
    for(int i = 0; i < m; i++){
        if(e[i].l >= st) continue;
        e[i].l += n, e[i].r += n;
        // if(e[i].l < st) e[i].l += n;
        // if(e[i].r < e[i].l) e[i].r += n;
        // cout<<e[i].l<<" "<<e[i].r<<"\n";
    }
    sort(e.begin(), e.end());
    assert(e[0].l == st);
    int r = e[0].l - 1;
    vector<int> ans(m);
    int id = 0;
    priority_queue<seg, vector<seg>, comp> q;
    int dist = 0;
    while(true){
        // cout<<"r : "<<r<<"\n";
        while(id < m && e[id].l <= r + 1){
            // cout<<"push : "<<e[id].l<<" "<<e[id].r<<" "<<e[id].id<<"\n";
            q.push(e[id]);
            id++;
        }
        while(true){
            if(q.empty()){
                cout<<"impossible\n";
                return 0;
            }
            seg cur = q.top(); q.pop();
            if(!ck(cur)) continue;
            if(cur.r <= r) continue;
            // cout<<"use : "<<cur.l<<" "<<cur.r<<" "<<cur.id<<"\n";
            insert(cur.l, cur.r, -1);
            ans[cur.id] = 1;
            dist += cur.r - r;
            r = cur.r;
            break;
        }
        // cout<<dist<<"\n";
        if(dist >= n) break;
    }
    // cout<<"ok\n";
    for(auto x : ans) cout<<x;
    cout<<"\n";
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10180 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 28 ms 7388 KB Output is correct
4 Correct 24 ms 7632 KB Output is correct
5 Correct 63 ms 12480 KB Output is correct
6 Correct 56 ms 9412 KB Output is correct
7 Correct 55 ms 14864 KB Output is correct
8 Incorrect 4 ms 5468 KB 'impossible' claimed, but there is a solution
9 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

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