oj.uz

Submission #941360

# Submission time Handle Problem Language Result Execution time Memory
941360 2024-03-08T15:48:23 Z phoenix0423 Alternating Current (BOI18_alternating) C++17
19 / 100
 96 ms 24860 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--;
        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 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:105:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i < nw.size(); i++){
      |                    ~~^~~~~~~~~~~
alternating.cpp:123:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int i = 0; i < nw.size(); i++){
      |                        ~~^~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 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 1 ms 5212 KB Output is correct
7 Correct 1 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 2 ms 7264 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 9308 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 1 ms 5212 KB Output is correct
7 Correct 1 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 2 ms 7264 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 9308 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 1 ms 5212 KB Output is correct
7 Correct 1 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 2 ms 7264 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 17632 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 58 ms 18164 KB Output is correct
4 Correct 27 ms 15072 KB Output is correct
5 Correct 61 ms 23968 KB Output is correct
6 Correct 96 ms 24240 KB Output is correct
7 Correct 58 ms 23392 KB Output is correct
8 Correct 5 ms 15288 KB Output is correct
9 Correct 4 ms 13148 KB Output is correct
10 Correct 67 ms 24860 KB Output is correct
11 Correct 58 ms 21844 KB Output is correct
12 Correct 49 ms 18360 KB Output is correct
13 Correct 2 ms 9564 KB Output is correct
14 Correct 2 ms 11612 KB Output is correct
15 Correct 62 ms 20452 KB Output is correct
16 Correct 50 ms 20684 KB Output is correct
17 Correct 74 ms 22192 KB Output is correct
18 Correct 64 ms 17844 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 58 ms 22964 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 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 1 ms 5212 KB Output is correct
7 Correct 1 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 2 ms 7264 KB Output is correct
12 Incorrect 1 ms 7260 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -