Submission #1068979

#TimeUsernameProblemLanguageResultExecution timeMemory
1068979Joshua_AnderssonMechanical Doll (IOI18_doll)C++14
10 / 100
79 ms9552 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; const int inf = int(1e9); typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> p2; #define rep(i, high) for (int i = 0; i < high; i++) #define repp(i, low, high) for (int i = low; i < high; i++) #define repe(i, container) for (auto& i : container) #define sz(container) ((int)container.size()) #define all(x) begin(x),end(x) #if _LOCAL #define assert(x) if (!(x)) __debugbreak() #endif int n; int ind = 1; vi state; vi x, y; int k=0; int numexits = 0; int build_tree(int d, vi& x, vi& y) { int u = ind++; if (d==0) { numexits += 2; x[u] = inf; y[u] = inf; return u; } y[u] = build_tree(d - 1, x, y); if (ind + (1 << (d - 1)) <= n + k + 20) { x[u] = build_tree(d - 1, x, y); } else x[u] = 1; return u; } int* lastv = 0; int statesum = 0; void traverse(int u, int t) { //cout << u << " "; int& v = state[u]?y[u]:x[u]; if (v == -1) return; statesum += state[u] == 0 ? 1 : -1; state[u] ^= 1; if (v==inf) { lastv = &v; v = -t; return; } traverse(v, t); } void create_circuit(int m, std::vector<int> a) { n = sz(a); vi c(m + 1, -1); c[0] = a[0]; n--; a.erase(a.begin()); while ((1<<(k+1))<=n) { k++; } state.resize(1 << (k+1)); x.resize(1 << (k+1), inf); y.resize(1 << (k+1), inf); build_tree(k, x, y); /*rep(i, sz(x)) { if (x[i]!=inf) cout << (i) << " " << x[i] << "\n"; if (y[i] != inf) cout << (i) << " " << y[i] << "\n"; }*/ rep(i, n) { traverse(1, a[i]); } repp(i, n, (1<<(k+1))) { traverse(1, -1); if (statesum == 0) { *lastv = 0; //cout << "ASD"; break; } //cout << "\n"; } rep(i, sz(x)) x[i] *= -1, y[i] *= -1; rep(i, sz(x)) { if (x[i] == -inf) x[i] = -1; if (y[i] == -inf) y[i] = -1; } x.erase(x.begin()); y.erase(y.begin()); /*int u = sz(x); rep(i, sz(x)) { cout << -(i+1) << " " << x[i] << "\n"; cout << -(i+1) << " " << y[i] << "\n"; }*/ 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...