Submission #414235

#TimeUsernameProblemLanguageResultExecution timeMemory
414235sofapudenMechanical Doll (IOI18_doll)C++14
37 / 100
150 ms13512 KiB
#include "doll.h" #include<bits/stdc++.h> using namespace std; vector<int> X, Y; vector<int> nX, nY; void fin(int x, int n, int par, bool ok, int val, vector<int> &A, bool flag){ if((x|val) >= n){ if(ok)X[par] = A[x]; else Y[par] = A[x]; } else{ int no = X.size(); if(!flag){ if(ok)X[par] = -no-1; else Y[par] = -no-1; } X.push_back(0); Y.push_back(0); fin(x,n,no,1,val<<1,A,0); fin(x|val,n,no,0,val<<1,A,0); } } void create_circuit(int m, vector<int> A) { A.push_back(-1); int n = A.size(); while((int)A.size() < (1<<(int)ceil(log2(n)))){ A.push_back(-1); } A.back() = 0; n = A.size(); vector<int> C(m + 1,-1); vector<int> H(m + 1); fin(0,n,-1,0,1,A,1); n = X.size(); set<int> bad; for(int i = n-1; i >= 0; --i){ if(X[i] < 0 && bad.count(X[i]))X[i] = X[-X[i]-1]; if(Y[i] < 0 && bad.count(Y[i]))Y[i] = Y[-Y[i]-1]; if(X[i] == Y[i])bad.insert(-(i+1)); } vector<int> trans; int cn = -1; for(int i = 0; i < n; ++i){ trans.push_back(cn); if(bad.count(-i-1))continue; nX.push_back(X[i]); nY.push_back(Y[i]); cn--; } //~ for(int i : X)cout << i << " "; //~ cout << "\n"; //~ for(int i : Y)cout << i << " "; //~ cout << "\n"; //~ for(int i : nX)cout << i << " "; //~ cout << "\n"; //~ for(int i : nY)cout << i << " "; //~ cout << "\n"; for(int &i : nX){if(i < 0)i = trans[-i-1];} for(int &i : nY){if(i < 0)i = trans[-i-1];} answer(C, nX, nY); }
#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...