oj.uz

Submission #941368

# Submission time Handle Problem Language Result Execution time Memory
941368 2024-03-08T16:01:00 Z phoenix0423 Alternating Current (BOI18_alternating) C++17
19 / 100
 92 ms 25016 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;
vector<int> adj[maxn];
 
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;
    }
} ee[maxn];
 
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;
        }
};
struct segtree{
    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, int L, int R){
        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]);
    }
    void upd(int l, int r, int val){ upd(l, r, val, 1, 0, n - 1);}
    int qry(int l, int r, int v, int L, int R){
        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));
    }
    int qry(int l, int r){ return qry(l, r, 1, 0, n - 1);}
    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);
    }
} st[2];
 
signed main(void){
    fastio;
    cin>>n>>m;
    vector<seg> e;
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        if(a == b + 1) a = 0, b = n - 1;
        ee[i] = seg(a, b, i);
        e.pb(seg(a, b, i));
        if(a <= b) e.pb(seg(a + n, b + n, i));
    }
    vector<int> par(m, -1);
    sort(e.begin(), e.end());
    int tr = -1, tid = -1;
    set<int> vis;
    vector<seg> nw;
    for(int i = 0; i < m; i++){
        auto [l, r, id] = e[i];
        if(r <= tr) par[id] = tid;
        else tr = r, tid = id;
    }
    for(int i = 0; i < m; i++){
        if(par[i] == -1) nw.pb(ee[i]);
        else{
            while(par[par[i]] != -1) par[i] = par[par[i]];
            adj[par[i]].pb(i);
        }
    }
    sort(nw.begin(), nw.end());
    vector<int> ans(m);
    for(int i = 0; i < nw.size(); i++){
        st[i % 2].insert(nw[i].l, nw[i].r, 1);
        ans[nw[i].id] = i % 2;
        for(auto id : adj[nw[i].id]){
            st[(i % 2 == 0)].insert(ee[id].l, ee[id].r, 1);
            ans[id] = (i % 2 == 0);
        }
    }
    if(st[0].qry(0, n - 1) >= 1 && st[1].qry(0, n - 1) >= 1){
        for(auto x : ans) cout<<x;
        cout<<"\n";
        return 0;
    }
    if(nw.size() % 2 == 0){
        cout<<"impossible\n";
        return 0;
    }
    else{
        for(int i = 0; i < nw.size(); i++){
            st[i % 2].insert(nw[i].l, nw[i].r, -1);
            st[(i % 2 == 0)].insert(nw[i].l, nw[i].r, 1);
            ans[nw[i].id] ^= 1;
            for(auto id : adj[nw[i].id]){
                st[(i % 2 == 0)].insert(ee[id].l, ee[id].r, -1);
                st[i % 2].insert(ee[id].l, ee[id].r, 1);
                ans[id] ^= 1;
            }
            if(st[0].qry(0, n - 1) >= 1 && st[1].qry(0, n - 1) >= 1){
                for(auto x : ans) cout<<x;
                cout<<"\n";
                return 0;
            }
        }
        cout<<"impossible\n";
    }
 
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:109:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i = 0; i < nw.size(); i++){
      |                    ~~^~~~~~~~~~~
alternating.cpp:127:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int i = 0; i < nw.size(); i++){
      |                        ~~^~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 7260 KB Output is correct
12 Incorrect 1 ms 7260 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 7260 KB Output is correct
12 Incorrect 1 ms 7260 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 7260 KB Output is correct
12 Incorrect 1 ms 7260 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 17620 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Correct 50 ms 18880 KB Output is correct
4 Correct 30 ms 15036 KB Output is correct
5 Correct 67 ms 23732 KB Output is correct
6 Correct 92 ms 25016 KB Output is correct
7 Correct 52 ms 23476 KB Output is correct
8 Correct 5 ms 14876 KB Output is correct
9 Correct 4 ms 13280 KB Output is correct
10 Correct 64 ms 24424 KB Output is correct
11 Correct 46 ms 22200 KB Output is correct
12 Correct 49 ms 17848 KB Output is correct
13 Correct 2 ms 9564 KB Output is correct
14 Correct 2 ms 11612 KB Output is correct
15 Correct 54 ms 19916 KB Output is correct
16 Correct 51 ms 20172 KB Output is correct
17 Correct 76 ms 20960 KB Output is correct
18 Correct 63 ms 18896 KB Output is correct
19 Correct 10 ms 14420 KB Output is correct
20 Correct 58 ms 22256 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 7260 KB Output is correct
12 Incorrect 1 ms 7260 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -