Submission #815353

#TimeUsernameProblemLanguageResultExecution timeMemory
815353rnl42Mechanical Doll (IOI18_doll)C++14
53 / 100
96 ms16856 KiB
//#include <bits/stdc++.h> #include "doll.h" using namespace std; int M, N; vector<int> A; vector<vector<int>> nexts; vector<int> C, X, Y; vector<bool> state; void push(int* pos, int val) { while (*pos < 0) { state[-*pos-1].flip(); pos = !state[-*pos-1] ? &X[-*pos-1] : &Y[-*pos-1]; } int prev = *pos; *pos = -1-(int)X.size(); state.push_back(true); X.push_back(prev); Y.push_back(val); } void create_circuit(int __M, vector<int> __A) { M = __M; A = __A; N = A.size(); nexts.resize(M+1); for (int i = 0; i < N-1; i++) { nexts[A[i]].push_back(A[i+1]); } nexts[A[N-1]].push_back(0); C.resize(M+1); X.reserve(3*N); Y.reserve(3*N); C[0] = A[0]; for (int node = 1; node <= M; node++) { if (!nexts[node].empty()) { C[node] = nexts[node].front(); int* root = &C[node]; for (int i = 1; i < (int)nexts[node].size(); i++) { push(root, nexts[node][i]); } } } vector<int*> todo; for (int i = 0; i <= M; i++) { if (C[i] < 0) { const int missing = (1<<__lg(2*(int)nexts[i].size()-1))-(int)nexts[i].size(); if (missing > 0) { for (int _ = 0; _ < missing; _++) { todo.push_back(&C[i]); } } } } if (!todo.empty()) { for (int i = 0; i < (int)todo.size()-1; i++) { push(todo[i], *todo[i+1]); } const int lastswitch = -1-(int)X.size(); for (auto& k : C) if (k == 0) { k = lastswitch; break; } for (auto& k : X) if (k == 0) { k = lastswitch; break; } for (auto& k : Y) if (k == 0) { k = lastswitch; break; } X.push_back(*todo[0]); Y.push_back(0); push(todo.back(), lastswitch); } 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...