Submission #978151

#TimeUsernameProblemLanguageResultExecution timeMemory
978151happypotatoMechanical Doll (IOI18_doll)C++17
53 / 100
106 ms16616 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define ff first #define ss second #define pb push_back void create_circuit(int m, vector<int> a) { int n = a.size(); int reidx[m + 1]; for (int i = 1; i <= m; i++) reidx[i] = 0; for (int x : a) reidx[x]++; int bruh[m + 1]; for (int i = 1; i < n; i++) bruh[a[i - 1]] = a[i]; bruh[a[n - 1]] = 0; int base = 0; vector<int> C(m + 1); C[0] = a[0]; for (int i = 1; i <= m; i++) { if (reidx[i] == 0) { C[i] = 0; } else if (reidx[i] == 1) { C[i] = bruh[i]; reidx[i] = 0; } else if (reidx[i] >= 2) { reidx[i] = ++base; C[i] = -reidx[i]; } } vector<int> sto[base + 1]; for (int i = 1; i < n; i++) { sto[reidx[a[i - 1]]].pb(a[i]); } sto[reidx[a[n - 1]]].pb(0); // for (int i = 1; i <= m; i++) cerr << reidx[i] << ' '; // cerr << endl; // for (int i = 1; i <= base; i++) { // for (int x : sto[i]) cerr << x << ' '; // cerr << endl; // } vector<pii> nxt[2]; bool flag = false; vector<int> access; vector<bool> state; auto gentree = [&](auto&& self, int sz) { if (sz == 2) { nxt[flag] = {{-2, -2}}; return; } self(self, (sz + 1) / 2); flag ^= 1; nxt[flag] = {{-1, -1}}; for (int i = 0; i < 2; i++) { int buff = nxt[flag].size(); if (i == 0) nxt[flag][0].ff = buff; else nxt[flag][0].ss = buff; for (pii cur : nxt[flag ^ 1]) { if (cur.ff != -2) cur.ff += buff; if (cur.ss != -2) cur.ss += buff; nxt[flag].pb(cur); } } if (sz % 2 == 1) { access.resize(nxt[flag].size(), 0); int st = 0; while (true) { if (!access[st]) { access[st] = !access[st]; if (nxt[flag][st].ff == -2) { nxt[flag][st].ff = 0; break; } st = nxt[flag][st].ff; } else { access[st] = !access[st]; if (nxt[flag][st].ss == -2) { nxt[flag][st].ss = 0; break; } st = nxt[flag][st].ss; } } } }; auto gen = [&](auto&& self, int sz) -> int { nxt[0].clear(); nxt[1].clear(); flag = false; gentree(gentree, sz); int used = nxt[flag].size(); int dirs = used; state.resize(used, 0); access.clear(); int cnt = 0; // cerr << "Gen size " << sz << ":\n"; // for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl; // cerr << "End" << endl; do { int st = 0; while (true) { if (!state[st]) { state[st] = !state[st]; cnt++; if (nxt[flag][st].ff == -2) { nxt[flag][st].ff = dirs++; break; } else { st = nxt[flag][st].ff; } } else { state[st] = !state[st]; cnt--; if (nxt[flag][st].ss == -2) { nxt[flag][st].ss = dirs++; break; } else { st = nxt[flag][st].ss; } } } } while (cnt > 0); // cerr << "Gen size " << sz << ":\n"; // for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl; // cerr << "End" << endl; return used; }; vector<int> X(base), Y(base); int cnt = base; for (int i = 1; i <= base; i++) { if (sto[i].size() == 1) { X[i - 1] = -i; Y[i - 1] = sto[i].front(); continue; } int assign = gen(gen, sto[i].size()); auto decrypt = [&](int x) -> int { if (x == 0) return -i; else if (x < assign) return -(x + cnt); else return sto[i][x - assign]; }; // cerr << "Gen " << i << ": \n"; // cerr << assign << endl; // for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl; // cerr << "End of gen " << i << endl; X[i - 1] = decrypt(nxt[flag][0].ff); Y[i - 1] = decrypt(nxt[flag][0].ss); for (int j = 1; j < (int)(nxt[flag].size()); j++) { // cerr << "decrypt " << nxt[j].ff << ' ' << decrypt(nxt[j].ff) << endl; X.pb(decrypt(nxt[flag][j].ff)); Y.pb(decrypt(nxt[flag][j].ss)); } cnt = (int)(X.size()); } answer(C, X, Y); }
#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...