Submission #238348

#TimeUsernameProblemLanguageResultExecution timeMemory
238348JatanaMechanical Doll (IOI18_doll)C++17
12 / 100
1095 ms8928 KiB
#include "doll.h" #include <iostream> #include <algorithm> #include <cassert> #include <random> #include <map> #define le(v) ((int)v.size()) #define pb push_back using namespace std; vector<int> X, Y; int inc = 0; int go(int outs) { int id = le(X); X.pb(-1e9); Y.pb(-1e9); if (outs > 2) { if (outs & 1) { outs++; inc++; } X[id] = go(outs / 2); Y[id] = go(outs / 2); } else assert(outs == 2); return -(id + 1); } vector<int> gen(int k) { if (k == 0) return {0}; vector<int> sub = gen(k - 1); vector<int> real; for (int i = 0; i < le(sub); i++) { real.pb(sub[i]); real.pb(sub[i] + (1 << (k - 1))); } return real; } vector<int> inv(vector<int> p) { vector<int> q(le(p)); for (int i = 0; i < le(p); i++) { q[p[i]] = i; } return q; } mt19937 rng(1337); void create_circuit(int M, vector<int> A) { X.clear(); Y.clear(); int N = A.size(); int cur = A[0]; A.insert(A.begin(), 0); map<int, int> cnt; for (int i = 0; i < le(A); i++) { cnt[A[i]]++; } vector<int> C(M + 1, -1e9); vector<int> B; int sz = 0; for (int i = 0; i < le(A); i++) { if (cnt[A[i]] == 1) { C[A[i]] = (i + 1 < le(A)) ? A[i + 1] : 0; } else { sz++; B.pb((i + 1 < le(A)) ? A[i + 1] : 0); } } inc = 0; int root = go(max(sz, 2)); if (B.empty()) { for (int i = 0; i < le(C); i++) { if (C[i] == -1e9) C[i] = 0; } for (int x : C) { cerr << x << " "; } cerr << endl; answer(C, {}, {}); return; } for (int i = 0; i < le(C); i++) { if (C[i] == -1e9) C[i] = root; } int wait = inc; A = B; reverse(A.begin(), A.end()); while (cur) { cerr << cur << " "; if (cur > 0) { cur = C[cur]; } else { cur = (-cur) - 1; if (X[cur] == -1e9) { bool cond = (wait + le(A)) % 2; // bool cond = true; // bool cond = binary_search(order[real].begin(), order[real].end(), it[real]); if (wait && ((le(A) == 1) || cond)) { wait--; X[cur] = root; } else { // cout << "decide" << endl; X[cur] = A.back(); A.pop_back(); } } swap(X[cur], Y[cur]); cur = Y[cur]; } } cerr << endl; for (int x : C) { cerr << x << " "; } cerr << endl; for (int i = 0; i < le(X); i++) { cerr << X[i] << " " << Y[i] << endl; } answer(C, X, Y); return; vector<bool> del(le(X), false); for (int it = 0; it < 100; it++) { for (int i = 0; i < le(X); i++) { if (del[i]) continue; if (X[i] < 0) { int j = (-X[i]) - 1; if (X[j] == Y[j]) { X[i] = X[j]; del[j] = true; } } if (Y[i] < 0) { int j = (-Y[i]) - 1; if (X[j] == Y[j]) { Y[i] = X[j]; del[j] = true; } } } for (int i = 0; i < le(C); i++) { if (C[i] < 0) { int j = (-C[i]) - 1; if (X[j] == Y[j]) { C[i] = X[j]; del[j] = true; } } } if (it == 0) { int killed = 0; for (int x : del) killed++; // cout << "killed: " << killed << endl; } } vector<int> alive; for (int i = 0; i < le(X); i++) { if (!del[i]) { alive.pb(i); } } for (int i = 0; i < le(X); i++) { if (X[i] < 0) { int id = lower_bound(alive.begin(), alive.end(), (-X[i]) - 1) - alive.begin(); X[i] = -(id + 1); } if (Y[i] < 0) { int id = lower_bound(alive.begin(), alive.end(), (-Y[i]) - 1) - alive.begin(); Y[i] = -(id + 1); } } for (int i = 0; i < le(C); i++) { if (C[i] < 0) { int id = lower_bound(alive.begin(), alive.end(), (-C[i]) - 1) - alive.begin(); C[i] = -(id + 1); } } int jump = 0; for (int i = 0; i < le(X); i++) { if (del[i]) { jump++; } else { X[i - jump] = X[i]; Y[i - jump] = Y[i]; } } X.resize(le(X) - jump); Y.resize(le(Y) - jump); // for (int x : del) { // cout << x << " "; // } // cout << endl; // for (int i = 0; i < le(X); i++) { // cout << X[i] << " " << Y[i] << endl; // } answer(C, X, Y); }

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:150:13: warning: unused variable 'x' [-Wunused-variable]
  150 |    for (int x : del) killed++;
      |             ^
doll.cpp:49:6: warning: unused variable 'N' [-Wunused-variable]
   49 |  int N = A.size();
      |      ^
#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...