oj.uz

답안 #941361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941361 2024-03-08T15:49:42 Z phoenix0423 Alternating Current (BOI18_alternating) C++17
19 / 100
 105 ms 24856 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{
            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:108:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i = 0; i < nw.size(); i++){
      |                    ~~^~~~~~~~~~~
alternating.cpp:126:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for(int i = 0; i < nw.size(); i++){
      |                        ~~^~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 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 5208 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 7084 KB Output is correct
12 Incorrect 2 ms 7260 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 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 5208 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 7084 KB Output is correct
12 Incorrect 2 ms 7260 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 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 5208 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 7084 KB Output is correct
12 Incorrect 2 ms 7260 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 17608 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 49 ms 18288 KB Output is correct
4 Correct 27 ms 15048 KB Output is correct
5 Correct 67 ms 23364 KB Output is correct
6 Correct 105 ms 23944 KB Output is correct
7 Correct 53 ms 21676 KB Output is correct
8 Correct 5 ms 14876 KB Output is correct
9 Correct 4 ms 13148 KB Output is correct
10 Correct 71 ms 24856 KB Output is correct
11 Correct 45 ms 22132 KB Output is correct
12 Correct 50 ms 19340 KB Output is correct
13 Correct 2 ms 9560 KB Output is correct
14 Correct 2 ms 11612 KB Output is correct
15 Correct 58 ms 19920 KB Output is correct
16 Correct 52 ms 20876 KB Output is correct
17 Correct 84 ms 22244 KB Output is correct
18 Correct 63 ms 19128 KB Output is correct
19 Correct 7 ms 14420 KB Output is correct
20 Correct 58 ms 23476 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 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 5208 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 7084 KB Output is correct
12 Incorrect 2 ms 7260 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -