제출 #525011

#제출 시각아이디문제언어결과실행 시간메모리
525011Redhood자동 인형 (IOI18_doll)C++14
6 / 100
120 ms36580 KiB
#include<bits/stdc++.h> #define fi first #define se second #define sz(x) (int)(x).size() #define all(x) (x).begin(),(x).end() #define pb push_back #include "doll.h" typedef long long ll; typedef long double ld; using namespace std; const int N = (int)1e6 + 10; int lst = 0; vector<int>trans[N]; int m; int x[N],y[N]; int build(vector<int>k, int ROOT){ if(sz(k) == 1){ if(k[0] == -1){ x[lst]=lst; y[lst]=ROOT; lst++; return lst-1; } return k[0]; } // assert(sz(k) != 0); vector<int>st[2]; if(sz(k) % 2 != 0) k.insert(k.begin(), -1); for(int i = 0; i < sz(k); ++i) st[i&1].pb(k[i]); // if(sz(st[0])>sz(st[1])){ // st[1].insert(st[1].begin(),-1); // } int v = lst++; if(ROOT==-1){ ROOT = v; } int A=build(st[0],ROOT),B=build(st[1],ROOT); x[v]=A; y[v]=B; return v; } int code(int f){ if(f <= m) return f; return -(f-m); } bool good(int f){ int pw=1; int F = f; while(f){ f>>=1; pw<<=1; } pw>>=1; if(pw==F) return true; return false; } void create_circuit(int M, std::vector<int> A){ m = M; A.push_back(0); A.insert(A.begin(), 0); for(int i = 0; i < sz(A) - 1; ++i){ trans[A[i]].push_back(A[i + 1]); } lst = M + 1; vector < int > C(M + 1); for(int i = 0; i <= M; ++i){ if(sz(trans[i]) == 0) continue; // reverse(all(trans[i])); // while(!good(sz(trans[i]))){ // trans[i].pb(-1); // } // reverse(all(trans[i])); // cout << " SZ " << sz(trans[i]) << endl; if(sz(trans[i]) == 1){ C[i] = trans[i][0]; }else{ C[i] = code(build(trans[i], -1)); } } vector<int>X(lst-1-M),Y(lst-1-M); for(int f=0;f<sz(X);++f){ X[f]=code(x[M+1+f]); Y[f]=code(y[M+1+f]); } // cout << "LOL \n"; // for(int i = 0; i <= M; ++i) // cout << C[i] << '\n'; // for(int f = 0; f < sz(X); ++f){ // cout << X[f] << ' ' << Y[f] << endl; // } // cout << endl; answer(C,X,Y); } /* 4 6 1 2 1 3 1 4 */
#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...