Submission #1191242

#TimeUsernameProblemLanguageResultExecution timeMemory
1191242MatteoArcari자동 인형 (IOI18_doll)C++20
53 / 100
130 ms43796 KiB
#include <bits/stdc++.h> using namespace std; void answer(vector<int> c, vector<int> x, vector<int> y); namespace { constexpr int P_MAX = 20000000; constexpr int S_MAX = 400000; int M, N; std::vector<int> A; bool answered; int S; std::vector<int> IC, IX, IY; void wrong_answer(const char *MSG) { exit(1); } void simulate() { if (S > S_MAX) { char str[50]; exit(0); } for (int i = 0; i <= M; ++i) { if (!(-S <= IC[i] && IC[i] <= M)) { wrong_answer("wrong serial number"); } } for (int j = 1; j <= S; ++j) { if (!(-S <= IX[j - 1] && IX[j - 1] <= M)) { wrong_answer("wrong serial number"); } if (!(-S <= IY[j - 1] && IY[j - 1] <= M)) { wrong_answer("wrong serial number"); } } int P = 0; std::vector<bool> state(S + 1, false); int pos = IC[0]; int k = 0; for (;;) { if (pos < 0) { if (++P > P_MAX) { char str[50]; exit(0); } state[-pos] = !state[-pos]; pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)]; } else { if (pos == 0) { break; } if (k >= N) { wrong_answer("wrong motion"); } if (pos != A[k++]) { wrong_answer("wrong motion"); } pos = IC[pos]; } } if (k != N) { wrong_answer("wrong motion"); } for (int j = 1; j <= S; ++j) { if (state[j]) { exit(0); } } } } // namespace void _answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y) { if (answered) { wrong_answer("answered not exactly once"); } answered = true; // check if input format is correct if ((int)C.size() != M + 1) { wrong_answer("wrong array length C"); } if (X.size() != Y.size()) { wrong_answer("wrong array length XY"); } S = X.size(); IC = C; IX = X; IY = Y; } void create_circuit(int m, vector<int> a) { int n = a.size(); A = a; N = n; M = m; vector<int> c(m + 1), x, y; vector<vector<int>> cnt(m + 1); cnt[0].push_back(a[0]); a.push_back(0); for (int i = 0; i < n; i++) { cnt[a[i]].push_back(a[i + 1]); } c[0] = a[0]; queue<int> s; vector<vector<int>> to; for (int i = 1; i <= m; i++) { if (cnt[i].size() == 0) { c[i] = 0; continue; } if (cnt[i].size() == 1) { c[i] = cnt[i][0]; continue; } int j = x.size() + 1; c[i] = -j; s.push(j); x.push_back(-j); y.push_back(-j); to.push_back(cnt[i]); } while (!s.empty()) { int j = s.front(); s.pop(); if (to[j - 1].size() == 2) { x[j - 1] = to[j - 1][0]; y[j - 1] = to[j - 1][1]; continue; } vector<int> _a, _b; for (int i = 0; i < to[j - 1].size(); i++) { if (i & 1) _b.push_back(to[j - 1][i]); else _a.push_back(to[j - 1][i]); } if (_a.size() > _b.size()) { _b.push_back(_a.back()); _a.pop_back(); _a.push_back(-j); } int k = x.size() + 1; x[j - 1] = -k; x.push_back(-k); y.push_back(-k); to.push_back(_a); s.push(k); k++; y[j - 1] = -k; x.push_back(-k); y.push_back(-k); to.push_back(_b); s.push(k); } _answer(c, x, y); simulate(); 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...