Submission #669459

#TimeUsernameProblemLanguageResultExecution timeMemory
669459jiahngMechanical Doll (IOI18_doll)C++14
6 / 100
92 ms27288 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef pair<int,int> pi; typedef vector <int> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define maxn 300010 #define INF (ll)1e9 #define MOD 1000000007 typedef pair <vi, int> pvi; typedef pair <int,pi> ipi; typedef vector <pii> vpii; int N; vi adj[maxn]; vector <int32_t> X,Y; vi build_idx[19], rev_build_idx[19]; int lg2[maxn]; int32_t solve(int32_t x){ if (adj[x].size() == 1) return adj[x][0]; int sz = adj[x].size(); int build_sz = 1<<(63 - __builtin_clz(sz)); if (build_sz < sz) build_sz <<= 1; int offset = (int)X.size() - 1; FOR(i,1,build_sz-1){ X.pb(0); Y.pb(0); } FOR(i,2,build_sz-1){ if (i&1) Y[i/2+offset] = i; else X[i/2+offset] = i; } FOR(i,0,build_sz-1){ int idx = rev_build_idx[lg2[build_sz]][i] + build_sz; if (!adj[x].empty()){ if (idx & 1) Y[idx/2+offset] = adj[x].back(); else X[idx/2+offset] = adj[x].back(); adj[x].pop_back(); } } return -(offset+1+1); } void create_circuit(int32_t M, std::vector<int32_t> A) { N = A.size(); std::vector<int32_t> C(M + 1); FOR(i,0,N-2){ adj[A[i]].pb(A[i+1]); } adj[A[N-1]].pb(0); FOR(i,1,M) reverse(all(adj[i])); int x = 1; FOR(i,0,18){ lg2[x] = i; x <<= 1; } build_idx[1].pb(0); build_idx[1].pb(1); FOR(i,2,18){ aFOR(j, build_idx[i-1]) build_idx[i].pb(j), build_idx[i].pb(j+(1<<(i-1))); } FOR(i,1,18){ rev_build_idx[i] = vi(build_idx[i].size()); FOR(j,0,build_idx[i].size()-1) rev_build_idx[i][build_idx[i][j]] = j; } C[0] = A[0]; for (int i = 1; i <= M; ++i) if (!adj[i].empty()){ C[i] = solve(i); } 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...