Submission #318483

#TimeUsernameProblemLanguageResultExecution timeMemory
318483jhnah917Alternating Current (BOI18_alternating)C++14
0 / 100
163 ms12772 KiB
#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){ int S = s, E = e; 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(int s, int e){ return query(1, 0, n-1, s, e); } } 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; 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 a[i].eli = dq.back().x; } while(dq.size() && dq.front().e <= ed) a[dq[0].x].eli = ed_idx, dq.pop_front(); for(auto i : dq) v.push_back(i); 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); } } bool eval(){ int t1 = seg[0].query(0, n-1); int t2 = seg[1].query(0, n-1); assert(t1 >= 0 && t2 >= 0); return t1 > 0 && t2 > 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:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i=0; i<v.size(); i++) a[v[i].x].color = i % 2;
      |                  ~^~~~~~~~~
alternating.cpp: In function 'void odd()':
alternating.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=0; i<v.size(); i++) a[v[i].x].color = i % 2;
      |                  ~^~~~~~~~~
alternating.cpp:117:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i=0; i<v.size(); i++){
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...