Submission #643062

#TimeUsernameProblemLanguageResultExecution timeMemory
643062ghostwriterMechanical Doll (IOI18_doll)C++14
53 / 100
176 ms23972 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.h> #include "grader.cpp" #endif #define st first #define nd second #define pb push_back #define pf push_front #define _pb pop_back #define _pf pop_front #define lb lower_bound #define ub upper_bound #define mtp make_tuple #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; typedef pair<int, int> pi; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; typedef string str; template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); } template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; } #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i)) #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i)) #define EACH(i, x) for (auto &(i) : (x)) #define WHILE while #define file "TEST" mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); } /* Tran The Bao CTL - Da Lat Cay ngay cay dem nhung deo duoc cong nhan */ const int MAXM = 4e5 + 5; int d[MAXM]; namespace subtask123 { vi next[MAXM]; void create_circuit(int M, vi A) { vi C(M + 1, 0), X, Y; int N = sz(A); next[0].pb(A[0]); FOR(i, 0, N - 1) next[A[i]].pb(i == N - 1? 0 : A[i + 1]); int S = 0; FOR(i, 0, M) { if (next[i].empty()) { C[i] = 0; continue; } if (sz(next[i]) == 1) { C[i] = next[i][0]; continue; } if (sz(next[i]) == 2) { C[i] = --S; X.pb(next[i][0]); Y.pb(next[i][1]); continue; } if (sz(next[i]) == 3) { C[i] = --S; X.pb(S - 1); Y.pb(S - 2); --S; X.pb(next[i][0]); Y.pb(next[i][1]); --S; X.pb(S + 2); Y.pb(next[i][2]); continue; } C[i] = --S; X.pb(S - 1); Y.pb(S - 2); --S; X.pb(next[i][0]); Y.pb(next[i][2]); --S; X.pb(next[i][1]); Y.pb(next[i][3]); } answer(C, X, Y); } } namespace subtask456 { int M, N, S = 0, d[MAXM], d1[MAXM]; vi A, X, Y; void add(int u, int x, int y) { WHILE(-u - 1 >= sz(X)) { X.pb(0); Y.pb(0); } X[-u - 1] = x; Y[-u - 1] = y; } vi build(int l, int r) { if (l == r) return {A[l]}; int mid = (l + r) / 2 - ((l + r) % 2 == 0? 1 : 0); vi left = build(l, mid); vi right = build(mid + 1, r); int root = --S; FOR(i, 1, sz(left) - 1) { int u = left[i], &x = X[-u - 1], &y = Y[-u - 1]; if (x == left[0]) x = root; if (y == left[0]) y = root; } FOR(i, 1, sz(right) - 1) { int u = right[i], &x = X[-u - 1], &y = Y[-u - 1]; if (x == right[0]) x = root; if (y == right[0]) y = root; } if (sz(left) < sz(right)) { if (sz(left) == 1) { int u = left[0]; --S; add(S, u, root); left = {S, S}; } else { vi nleft = {left[0]}; FOR(i, 1, sz(left) - 1) { int u = left[i]; int x = X[-u - 1], y = Y[-u - 1]; add(u, S - 1, S - 2); nleft.pb(S - 1); nleft.pb(S - 2); --S; add(S, x, root); --S; add(S, y, root); } swap(left, nleft); } } add(root, left[0], right[0]); vi ans = {root}; FOR(i, 1, sz(left) - 1) ans.pb(left[i]); FOR(i, 1, sz(right) - 1) ans.pb(right[i]); if (sz(left) == 1) ans.pb(root); return ans; } void create_circuit(int M, vi A) { A.pb(0); N = sz(A); subtask456::M = M; subtask456::A = A; vi ans = build(0, N - 1); int root = ans[0]; vi C(M + 1); FOR(i, 0, M) C[i] = root; int cur = 0, cnt = 0; WHILE(cnt < N) { int pre = cur; if (cur >= 0) cur = C[cur]; else if (!d[-cur - 1]) { d[-cur - 1] ^= 1; cur = X[-cur - 1]; } else { d[-cur - 1] ^= 1; cur = Y[-cur - 1]; } if (cur >= 0) { cur = A[cnt]; if (d[-pre - 1]) X[-pre - 1] = A[cnt++]; else Y[-pre - 1] = A[cnt++]; } } answer(C, X, Y); } } void create_circuit(int M, std::vector<int> A) { int N = A.size(); bool sub123 = 1; FOR(i, 0, N - 1) { ++d[A[i]]; if (d[A[i]] > 4) sub123 = 0; } if (sub123) { subtask123::create_circuit(M, A); return; } subtask456::create_circuit(M, A); } /* 3 5 5 5 1 1 3 */

Compilation message (stderr)

doll.cpp: In function 'void subtask123::create_circuit(int, vi)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:46:9: note: in expansion of macro 'FOR'
   46 |         FOR(i, 0, N - 1) next[A[i]].pb(i == N - 1? 0 : A[i + 1]);
      |         ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:48:9: note: in expansion of macro 'FOR'
   48 |         FOR(i, 0, M) {
      |         ^~~
doll.cpp: In function 'vi subtask456::build(int, int)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:105:9: note: in expansion of macro 'FOR'
  105 |         FOR(i, 1, sz(left) - 1) {
      |         ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:110:9: note: in expansion of macro 'FOR'
  110 |         FOR(i, 1, sz(right) - 1) {
      |         ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:124:17: note: in expansion of macro 'FOR'
  124 |                 FOR(i, 1, sz(left) - 1) {
      |                 ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:140:9: note: in expansion of macro 'FOR'
  140 |         FOR(i, 1, sz(left) - 1) ans.pb(left[i]);
      |         ^~~
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:141:9: note: in expansion of macro 'FOR'
  141 |         FOR(i, 1, sz(right) - 1) ans.pb(right[i]);
      |         ^~~
doll.cpp: In function 'void subtask456::create_circuit(int, vi)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:153:9: note: in expansion of macro 'FOR'
  153 |         FOR(i, 0, M) C[i] = root;
      |         ^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
doll.cpp:178:5: note: in expansion of macro 'FOR'
  178 |     FOR(i, 0, N - 1) {
      |     ^~~
#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...