Submission #318489

#	Time	Username	Problem	Language	Result	Execution time	Memory
318489		jhnah917	Alternating Current (BOI18_alternating)	C++14	100 / 100	169 ms	15192 KiB

alternating

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int par[101010];
vector<int> g[101010];
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
void merge(int pa, int ch){ pa = find(pa); ch = find(ch); if(pa != ch) par[ch] = pa; }

struct Seg{
    int tree[1 << 18], tmp[1 << 18], n;
    void init(int _n){ n = _n; memset(tree, 0, sizeof tree); memset(tmp, 0, sizeof tree); }
    void push(int node, int s, int e){
        if(!tmp[node]) return;
        tree[node] += tmp[node];
        if(s != e){
            tmp[node << 1] += tmp[node];
            tmp[node << 1 | 1] += tmp[node];
        }
        tmp[node] = 0;
    }
    void update(int node, int s, int e, int l, int r, int v){
        push(node, s, e);
        if(r < s || e < l) return;
        if(l <= s && e <= r){
            tmp[node] += v; push(node, s, e);
            return;
        }
        int m = s + e >> 1;
        update(node << 1, s, m, l, r, v);
        update(node << 1 | 1, m+1, e, l, r, v);
        tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
    }
    int query(int node, int s, int e, int l, int r){
        push(node, s, e);
        if(r < s || e < l) return 1e9;
        if(l <= s && e <= r) return tree[node];
        int m = s + e >> 1;
        int t1 = query(node << 1, s, m, l, r);
        int t2 = query(node << 1 | 1, m+1, e, l, r);
        return min(t1, t2);
    }
    void update(int s, int e, int x){
        if(e >= n) e -= n;
        if(s <= e) update(1, 0, n-1, s, e, x);
        else update(1, 0, n-1, 0, e, x), update(1, 0, n-1, s, n-1, x);
    }
    int query(){ return query(1, 0, n-1, 0, n-1); }
} seg[2];

struct Info{
    int s, e, x, eli, color;
    Info() : Info(0, 0, 0) {}
    Info(int s, int e, int x) : s(s), e(e), x(x), eli(-1), color(-1) {}
    bool operator < (const Info &t) const { return make_pair(s, -e) < make_pair(t.s, -t.e); }
};

int n, m, ed, ed_idx;
Info a[101010];
vector<Info> v;

int tmp[101010];

void calc_elimination(){
    deque<Info> dq;
    sort(a+1, a+m+1);
    for(int i=1; i<=m; i++){
        if(dq.empty() || dq.back().e < a[i].e) dq.push_back(a[i]);
        else tmp[a[i].x] = dq.back().x;
    }
    while(dq.size() && dq.front().e <= ed) tmp[dq[0].x] = ed_idx, dq.pop_front();
    for(auto i : dq) v.push_back(i);
    for(int i=1; i<=m; i++) if(tmp[a[i].x]) a[i].eli = tmp[a[i].x];
    
    iota(par, par+101010, 0);
    for(int i=1; i<=m; i++) if(a[i].eli != -1) merge(a[i].eli, a[i].x);
    for(int i=1; i<=m; i++){
        if(a[i].eli != -1) a[i].eli = find(a[i].x), g[a[i].eli].push_back(a[i].x);
        else g[a[i].x].push_back(a[i].x);
    }
}

inline bool eval(){ return seg[0].query() > 0 && seg[1].query() > 0; }

void even(){
    seg[0].init(n); seg[1].init(n);
    
    for(int i=0; i<v.size(); i++) a[v[i].x].color = i % 2;
    for(int i=1; i<=m; i++) if(a[i].color == -1) a[i].color = !a[a[i].eli].color;
    
    for(int i=1; i<=m; i++){
        seg[a[i].color].update(a[i].s, a[i].e, 1);
    }
    if(eval()){
        for(int i=1; i<=m; i++) cout << a[i].color;
    }
    else cout << "impossible";
}

void odd(){
    seg[0].init(n); seg[1].init(n);
    for(int i=0; i<v.size(); i++) a[v[i].x].color = i % 2;
    for(int i=1; i<=m; i++) if(a[i].color == -1) a[i].color = !a[a[i].eli].color;
    for(int i=1; i<=m; i++){
        seg[a[i].color].update(a[i].s, a[i].e, 1);
    }
    if(eval()){ for(int j=1; j<=m; j++) cout << a[j].color; return; }
    
    for(int i=0; i<v.size(); i++){
        for(auto j : g[v[i].x]){
            seg[a[j].color].update(a[j].s, a[j].e, -1);
            a[j].color ^= 1;
            seg[a[j].color].update(a[j].s, a[j].e, 1);
        }
        if(eval()){ for(int j=1; j<=m; j++) cout << a[j].color; return; }
    }
    cout << "impossible";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int s, e; cin >> s >> e; s--; e--;
        if(s > e){
            if(ed < e) ed = e, ed_idx = i;
            e += n;
        }
        a[i] = {s, e, i};
    }
    calc_elimination();
    sort(a+1, a+m+1, [](Info a, Info b){ return a.x < b.x; });
    if(v.size() % 2 == 0) even();
    else odd();
}

Compilation message (stderr)

alternating.cpp: In member function 'void Seg::update(int, int, int, int, int, int)':
alternating.cpp:34:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int m = s + e >> 1;
      |                 ~~^~~
alternating.cpp: In member function 'int Seg::query(int, int, int, int, int)':
alternating.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int m = s + e >> 1;
      |                 ~~^~~
alternating.cpp: In function 'void even()':
alternating.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0; i<v.size(); i++) a[v[i].x].color = i % 2;
      |                  ~^~~~~~~~~
alternating.cpp: In function 'void odd()':
alternating.cpp:107:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i=0; i<v.size(); i++) a[v[i].x].color = i % 2;
      |                  ~^~~~~~~~~
alternating.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26