제출 #396307

#제출 시각아이디문제언어결과실행 시간메모리
39630712tqian자동 인형 (IOI18_doll)C++17
0 / 100
2 ms204 KiB
#include <bits/stdc++.h> #include "doll.h" using namespace std; #define f1r(i, a, b) for (int i = a; i < b; ++i) #define f0r(i, a) f1r(i, 0, a) #define each(t, a) for (auto& t : a) #define pb push_back #define eb emplace_back #define mp make_pair #define f first #define s second #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pi; typedef vector<pi> vpi; typedef vector<ll> vl; typedef pair<ll, ll> pl; typedef vector<pl> vpl; using namespace std; void create_circuit(int m, vi a) { // example circuit // m is the number of triggers // n is the length of the sequence int n = sz(a); vi c(m + 1); if (n == 1) { f1r(i, 1, m + 1) { c[i] = 0; } c[0] = a[0]; answer(c, vi(), vi()); return; } // root switch at -1 f1r(i, 1, m + 1) { c[i] = -1; // connect to the root } c[0] = a[0]; a.erase(a.begin()); // erase first element a.pb(0); // add the beginning again // now from the root, we go to each number in some order // we need n exits // i -> 2 * i, 2 * i + 1 int d = 0; while ((1 << d) < n) d++; int sz = (1 << d); // this is the bottom row // leaf nodes are the exits int excess = sz - n; // stuff not used on bottom row vi dead(2 * sz); vi state(2 * sz); f0r(i, excess) { dead[sz + i] = 1; } function<void(int)> gather = [&](int u) { if (u >= sz) return; gather(2 * u); gather(2 * u + 1); dead[u] = (dead[2 * u] & dead[2 * u + 1]); }; gather(1); vi ord; f0r(i, n) { // go through each of the nodes int bot = -1; function<bool(int)> go = [&](int u) -> bool { if (u >= sz) { bot = u; return dead[u]; } else { if (state[u] == 0) { state[u] ^= 1; return go(2 * u); } else { state[u] ^= 1; return go(2 * u + 1); } } }; while (go(1)) {} ord.pb(bot); } map<int, int> xdest, ydest; f0r(i, sz(ord)) { int u = ord[i]; int p = u / 2; if (2 * p == u) { xdest[p] = a[i]; } else { ydest[p] = a[i]; } } vi used; function<void(int)> dfs = [&](int u) { if (dead[u]) { return; } if (u >= sz) { return; } else { used.pb(u); dfs(2 * u); dfs(2 * u + 1); } }; dfs(1); // cout << sz(used) << endl; auto get_pos = [&](int x) -> int { return lower_bound(all(used), x) - used.begin(); }; int s = sz(used); vi x(s); vi y(s); each(v, used) { int i = get_pos(v); if (2 * v < sz) { if (!dead[2 * v]) { int to = get_pos(2 * v); x[i] = -(to + 1); } else { x[i] = -1; } if (!dead[2 * v + 1]) { int to = get_pos(2 * v + 1); y[i] = -(to + 1); } else { y[i] = -1; } } else { if (!dead[2 * v]) { x[i] = xdest[v]; } else { x[i] = -1; } if (!dead[2 * v + 1]) { y[i] = ydest[v]; } else { y[i] = -1; } } } answer(c, x, y); auto output = [&](vi v) { each(x, v) cout << x << " "; cout << endl; }; // output(c); // output(x); // output(y); return; } /** * n + log2 switches for full credit * 1e5 triggers, 2e5 length sequence * P is like 20 * n, which is like log2(m) * n ish? * general observations * from a trigger you go to same switch every time * so you have a binary choice of next switch * 2n switches is easy * you can choose specifically which switches to ignore * if you make it into like sets of 2^k, and then just redirect them back to the beginning * the idea is you can figure out where to direct the things, i see * subtask 1 * make a ordered cycle * subtask 2 * if you go to some place twice, use the switch appropriately * subtask 3 * you can just do similarly to task 2 * subtask 4 * * subtask 5 * * subtask 6 * */

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:149:10: warning: variable 'output' set but not used [-Wunused-but-set-variable]
  149 |     auto output = [&](vi v) { each(x, v) cout << x << " "; cout << endl; };
      |          ^~~~~~
#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...