제출 #1240807

#제출 시각아이디문제언어결과실행 시간메모리
1240807fv3Sphinx's Riddle (IOI24_sphinx)C++20
100 / 100
69 ms1208 KiB
#include "sphinx.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) x.begin(), x.end() vector<int> find_colours(int n, vector<int> u, vector<int> v) { const int m = int(u.size()); vector<vector<int>> adj(n); for (int i = 0; i < m; i++) { adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]); } auto Count = [&](const vector<int>& S) { int components_cnt = 0; vector<bool> vis(n, false); for (int i = 0; i < n; i++) { if (vis[i]) continue; components_cnt++; queue<int> q; vis[i] = true; q.push(i); while (!q.empty()) { int cur = q.front(); q.pop(); for (int nxt : adj[cur]) { if (!vis[nxt] && S[nxt] == S[cur]) { vis[nxt] = true; q.push(nxt); } } } } return components_cnt; }; vector<int> blue(n, 0), blues; for (int i = 0; i < n; i++) { bool go_blue = true; for (auto node : adj[i]) { if (blue[node]) { go_blue = false; } } if (go_blue) { blue[i] = 1; blues.push_back(i); } } vector<int> colours(n, -1); // Find colour of all blue's for (int c = 0; c < n; c++) { vector<int> col(n, c); for (int i : blues) { col[i] = -1; } int initial_experiment = perform_experiment(col); while (!blues.empty() && Count(col) != initial_experiment) { int lo = 0, hi = int(blues.size()) - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; for (int i : blues) { col[i] = n; } for (int i = lo; i <= mid; i++) { col[blues[i]] = -1; } if (perform_experiment(col) == Count(col)) { lo = mid + 1; } else { hi = mid; } } col[blues[lo]] = c; colours[blues[lo]] = c; blues.erase(blues.begin() + lo); } } vector<int> id; for (int i = 0; i < n; i++) { if (!blue[i]) { id.push_back(i); } } mt19937 mt(time(0)); shuffle(all(id), mt); set<int> relevant_colours; int neutral; { vector<int> col(n, -1); for (int i = 0; i < n; i++) if (blue[i]) { col[i] = n; } int exp = perform_experiment(col); for (int c = 0; c < n; c++) { for (int i = 0; i < n; i++) if (blue[i]) { col[i] = c; } if (perform_experiment(col) != exp) { relevant_colours.insert(c); } } for (int c = 0; c < n; c++) { if (relevant_colours.count(c)) continue; neutral = c; break; } } map<pair<int, int>, set<int>> ranges; auto Solve = [&](auto&& self, int lo, int hi, const set<int>& s) -> void { assert(hi - lo + 1 >= int(s.size())); if (hi == lo) { colours[id[lo]] = *s.begin(); return; } int mid = lo + (hi - lo) / 2; if (s.size() == 1) { self(self, lo, mid, s); self(self, mid+1, hi, s); return; } set<int> l, r; auto Col = [&](int c, int tl, int tr) -> vector<int> { vector<int> col(n, n); for (int i = 0; i < n; i++) if (blue[i]) { col[i] = c; } for (int i = tl; i <= tr; i++) { col[id[i]] = -1; } return col; }; int exp_l = -1, exp_r = -1; for (int c : s) { if (int(l.size()) == mid - lo + 1) { r.insert(c); continue; } vector<int> col = Col(c, lo, mid); if (exp_l == -1) { exp_l = lo == mid ? Count(Col(neutral, lo, mid)) : perform_experiment(Col(neutral, lo, mid)); } if (perform_experiment(col) == exp_l) { r.insert(c); } else { l.insert(c); } } for (int c : s) { if (int(r.size()) == hi - mid) break; if (r.count(c)) continue; if (exp_r == -1) { exp_r = mid+1 == hi ? Count(Col(neutral, mid+1, hi)) : perform_experiment(Col(neutral, mid+1, hi)); } if (perform_experiment(Col(c, mid+1, hi)) != exp_r) { r.insert(c); } } self(self, lo, mid, l); self(self, mid+1, hi, r); }; Solve(Solve, 0, int(id.size())-1, relevant_colours); return colours; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...