# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
560708 | tfg | Mechanical Doll (IOI18_doll) | C++17 | 1 ms | 284 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "doll.h"
const int MAGIC = 1e9;
std::vector<int> X, Y;
int solve(int sz) {
int id = (int) X.size();
X.push_back(MAGIC), Y.push_back(MAGIC);
if(sz == 1) {
X[id] = -id-1;
} else if(sz > 2) {
X[id] = solve(sz/2);
Y[id] = solve(sz/2);
}
return -id-1;
}
int outerSolve(const std::vector<int> &A) {
int n = (int) A.size();
if(n == 1) {
solve(1);
Y.back() = A.back();
}
int id = 0;
while((1 << id) * 2 <= n) id++;
for(int i = 0; i < id; i++) {
X.push_back(((1 << (id - i)) & n) ? MAGIC : -1), Y.push_back(-(i+1)-1);
}
Y.back() = n % 2 ? MAGIC : -1;
for(int i = 0; i < id; i++) {
if(X[i] == MAGIC) {
X[i] = solve(1 << (id - i));
//std::cout << "tree for 2^" << (id-i) << " in " << X[i] << std::endl;
}
}
std::vector<bool> state(X.size(), false);
for(auto val : A) {
int on = -1;
//std::cout << "val is " << val << std::endl;
while(on < 0) {
//std::cout << "on " << on << std::endl;
//assert(on < 0);
state[-on-1] = !state[-on-1];
int &nxt = (state[-on-1] ? X : Y)[-on-1];
if(nxt >= 0) {
//assert(nxt == MAGIC);
nxt = val;
}
on = nxt;
}
//assert(on == val);
}
return -1;
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
std::vector<int> C(M + 1, -1);
C[0] = A[0];
A.erase(A.begin());
A.push_back(0);
outerSolve(A);
answer(C, X, Y);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |