Submission #299812

#TimeUsernameProblemLanguageResultExecution timeMemory
299812TangentMechanical Doll (IOI18_doll)C++17
100 / 100
285 ms23488 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; // typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order(), order_of_key() typedef long long ll; typedef long double dd; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<dd, dd> pdd; typedef vector<int> vii; typedef vector<ll> vll; typedef vector<dd> vdd; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<pdd> vpdd; typedef vector<vii> vvii; typedef vector<vll> vvll; typedef vector<vdd> vvdd; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; typedef vector<vpdd> vvpdd; typedef vector<bool> vb; const int inf = 1 << 30; #define rep(i, n) for (ll i = 0; i < n; i++) #define ffor(i, a, b) for(ll i = a; i < b; i++) #define forin(x, a) for (auto &x: a) #define all(x) x.begin(), x.end() #ifdef TEST #define dbg(x) cout << #x << ": " << x << '\n'; #define dbgc(x) cout << #x << ":"; forin(a, x) { cout << " " << a; } cout << endl; #define tassert(x) assert(x); #else #define dbg(x) #define dbgc(x) #define tassert(x) #endif void create_circuit(int M, std::vector<int> A) { int N = A.size(); map<int, int> counts; int max_count = 0; forin(x, A) { counts[x]++; max_count = max(max_count, counts[x]); } vii C(M + 1); if (max_count == 1) { rep(i, N - 1) { C[A[i]] = A[i + 1]; } C[0] = A[0]; C[A[N - 1]] = 0; answer(C, vii(), vii()); } else { C.assign(M + 1, -1); int p2 = 1, bits = 0; while (p2 < N + 1) { p2 <<= 1; bits++; } int curr = 0; map<int, int> order; rep(i, p2) { if (i >= p2 - N - 1) order[curr] = i; int x = 1 << (bits - 1); while (curr & x) { curr ^= x; x >>= 1; } curr ^= x; } int j = 0; vii seq(p2, -1); forin(p, order) { seq[p.second] = j++; } int l = p2; vii above = {0}, X, Y; rep(d, bits) { vii nabove; rep(i, 1 << d) { if (above[i >> 1] == -1) { nabove.emplace_back(-1); } else if (l * (i + 1) <= p2 - N - 1) { nabove.emplace_back(-1); if (i & 1) { Y[above[i >> 1]] = -1; } else { X[above[i >> 1]] = -1; } } else { X.emplace_back(-1); Y.emplace_back(-1); nabove.emplace_back(X.size() - 1); if (i & 1) { Y[above[i >> 1]] = -X.size(); } else { X[above[i >> 1]] = -X.size(); } } } above = move(nabove); l >>= 1; } A.emplace_back(0); rep(i, p2) { if (seq[i] >= 0) { if (i & 1) { Y[above[i >> 1]] = A[seq[i]]; } else { X[above[i >> 1]] = A[seq[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...