Submission #926955

#TimeUsernameProblemLanguageResultExecution timeMemory
926955GrindMachineMechanical Doll (IOI18_doll)C++17
53 / 100
119 ms14820 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "doll.h" void create_circuit(int m, std::vector<int> a) { // int N = A.size(); // std::vector<int> C(M + 1); // C[0] = -1; // for (int i = 1; i <= M; ++i) { // C[i] = 1; // } // std::vector<int> X(N), Y(N); // for (int k = 0; k < N; ++k) { // X[k] = Y[k] = A[k]; // } // answer(C, X, Y); int n = sz(a); vector<int> b(m+1); vector<int> pos[m+1]; rep(i,n) pos[a[i]].pb(i); vector<int> root(m+1); vector<int> sx(1), sy(1), flipped; int switch_ptr = 1; rep1(i,m){ if(sz(pos[i]) <= 1) conts; root[i] = -switch_ptr; sx.pb(0), sy.pb(0); switch_ptr++; } b[0] = a[0]; rep(i,n){ b[a[i]] = root[a[i]]; } ll last_guy = inf2, last_type = inf2; vector<pll> pending; rep1(x,m){ if(pos[x].empty()) conts; auto &p = pos[x]; int c = sz(p); if(c == 1){ ll i = p[0]; if(i+1 < n){ b[x] = a[i+1]; } else{ last_guy = x; } conts; } int siz = 1; while(siz < c) siz <<= 1; queue<pll> q; q.push({root[x],0}); ll depth = __lg(siz)-1; while(!q.empty()){ auto [u,d] = q.front(); q.pop(); if(d >= depth) conts; sx[-u] = -switch_ptr; sx.pb(0), sy.pb(0); switch_ptr++; sy[-u] = -switch_ptr; sx.pb(0), sy.pb(0); switch_ptr++; q.push({sx[-u],d+1}); q.push({sy[-u],d+1}); } while(sz(flipped) < sz(sx)){ flipped.pb(0); } rep1(iter,siz){ int ptr = root[x]; rep1(d,depth){ flipped[-ptr] ^= 1; if(flipped[-ptr]){ ptr = sx[-ptr]; } else{ ptr = sy[-ptr]; } } if(iter <= c){ ll i = p[iter-1]; if(i+1 < n){ ll nxt = a[i+1]; flipped[-ptr] ^= 1; if(flipped[-ptr]){ sx[-ptr] = nxt; } else{ sy[-ptr] = nxt; } } else{ last_guy = ptr; flipped[-ptr] ^= 1; if(flipped[-ptr]){ last_type = 0; } else{ last_type = 1; } } } else{ ll nxt = 0; if(iter < siz){ nxt = root[x]; flipped[-ptr] ^= 1; if(flipped[-ptr]){ sx[-ptr] = nxt; } else{ sy[-ptr] = nxt; } } else{ flipped[-ptr] ^= 1; pending.pb({root[x],ptr}); } } } // rep1(iter,siz){ // ll ptr = 1; // while(ptr < siz/2){ // flipped[ptr] ^= 1; // if(flipped[ptr]){ // ptr = ptr*2; // } // else{ // ptr = ptr*2+1; // } // } // ll nxt = 0; // if(iter < c){ // nxt = 1; // } // else if(iter < siz){ // nxt = -1; // } // else{ // nxt = 0; // } // flipped[ptr] ^= 1; // if(flipped[ptr]){ // sx[ptr] = nxt; // } // else{ // sy[ptr] = nxt; // } // } } assert(accumulate(all(flipped),0ll) == 0); pending.pb({0,0}); if(last_type == 0){ sx[-last_guy] = pending.front().ff; } else if(last_type == 1){ sy[-last_guy] = pending.front().ff; } else{ b[last_guy] = pending.front().ff; } rep(i,sz(pending)-1){ sy[-pending[i].ss] = pending[i+1].ff; } sx.erase(sx.begin()); sy.erase(sy.begin()); assert(sz(sx) <= 2*n); answer(b,sx,sy); // rep1(i,siz/2-1){ // sx[i] = -(i*2); // sy[i] = -(i*2+1); // } // rep1(iter,siz){ // ll ptr = 1; // while(ptr < siz/2){ // flipped[ptr] ^= 1; // if(flipped[ptr]){ // ptr = ptr*2; // } // else{ // ptr = ptr*2+1; // } // } // ll nxt = 0; // if(iter < n){ // nxt = 1; // } // else if(iter < siz){ // nxt = -1; // } // else{ // nxt = 0; // } // flipped[ptr] ^= 1; // if(flipped[ptr]){ // sx[ptr] = nxt; // } // else{ // sy[ptr] = nxt; // } // } // sx.erase(sx.begin()); // sy.erase(sy.begin()); // answer(b,sx,sy); // vector<int> cnt(m+1); // rep(i,n) cnt[a[i]]++; // rep(i,m+1){ // if(cnt[i] == 1){ // a.pb(i); // } // } // auto on = n; // n = sz(a); // b[0] = a[0]; // vector<int> switch_id(m+1,-1); // trigger i is connected to which switch? // int ptr = 1; // rep(i,n){ // int x = a[i]; // if(switch_id[x] == -1){ // switch_id[x] = ptr; // b[x] = -ptr; // sx.pb(0); // sy.pb(0); // if(i+1 < on){ // sx[ptr] = a[i+1]; // } // else if(i+1 < n){ // sx[ptr] = -switch_id[a[i+1]]; // } // ptr++; // } // else{ // b[x] = -switch_id[x]; // if(i+1 < on){ // sy[switch_id[x]] = a[i+1]; // } // else if(i+1 < n){ // sy[switch_id[x]] = -switch_id[a[i+1]]; // } // } // } // sx.erase(sx.begin()); // sy.erase(sy.begin()); // debug(b); // debug(sx); // debug(sy); // answer(b,sx,sy); }
#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...