Submission #336143

#TimeUsernameProblemLanguageResultExecution timeMemory
336143super_j6Mechanical Doll (IOI18_doll)C++14
10 / 100
4 ms4300 KiB
#include "doll.h" #include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; #define endl '\n' #define ll long long #define pi pair<int, int> #define f first #define s second #define vi vector<int> const int mxn = 1 << 19; int n, k, t; bool b[mxn]; vi f, u(mxn), v(mxn); int bld(int l, int r){ if(l == r) return 0; if(r < k - n - (n & 1)) return -1; int it = t++, mid = (l + r) / 2; u[it] = bld(l, mid), v[it] = bld(mid + 1, r); return -it - 1; } void add(int x, int y){ x = -x - 1; int &z = b[x] ? v[x] : u[x]; b[x] ^= 1; if(!z) z = y; else add(z, y); } /* void answer(vi f, vi u, vi v){ for(int i = 0; i < f.size(); i++){ cout << i << ": " << f[i] << endl; } for(int i = 0; i < u.size(); i++){ cout << (-i - 1) << ": " << u[i] << " " << v[i] << endl; } } */ void create_circuit(int m, vi a){ n = a.size(), k = 1 << (__lg(n - 1) + 1); bld(0, k - 1); for(int i = 1; i < n; i++) add(-1, a[i]); add(-1, 0); f.assign(m + 1, -1), u.resize(t), v.resize(t); f[0] = a[0]; answer(f, u, v); } /* int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vi a(n); for(int i = 0; i < n; i++) cin >> a[i]; create_circuit(m, a); return 0; } */
#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...