제출 #1231169

#제출 시각아이디문제언어결과실행 시간메모리
1231169chaeryeongLockpicking (IOI23_lockpicking)C++20
0 / 100
10 ms328 KiB
#include "lockpicking.h" #include <bits/stdc++.h> using namespace std; void construct_card (int n, vector <int> a, vector <vector <int>> S) { for (int i = 0; i < n; i++) { assert(S[i][0] == S[i][1]); } vector <array <int, 2>> trie = {{-1, -1}}; vector <int> node = {0}; vector <int> val = {0}; for (int i = 0; i < n; i++) { int x = i; vector <int> s; for (int j = 0; j + 1 < n; j++) { s.push_back(a[x]); x = S[x][0]; } int cur = 0; for (auto j : s) { if (trie[cur][j] == -1) { trie[cur][j] = (int)trie.size(); trie.push_back({-1, -1}); node.push_back(0); val.push_back(-1); } cur = trie[cur][j]; node[cur] = x; val[cur] = j; } } //n^2 so far int m = trie.size() + n; vector <vector <int>> T(m); vector <int> b(m); for (int i = 0; i < n; i++) { b[i] = a[i]; T[i] = S[i]; } for (int i = n; i < m; i++) { T[i] = {trie[i - n][0], trie[i - n][1]}; if (T[i][0] == -1 && T[i][1] == -1) { //if (i == 10) cout << val[i - n] << " || +" << node[i - n] << '\n'; T[i][a[node[i - n]]] = S[node[i - n]][0]; T[i][1 - a[node[i - n]]] = i; b[i] = 0; } else if (T[i][0] == -1) { T[i][1] += n; T[i][0] = i; b[i] = 0; } else if (T[i][1] == -1) { T[i][0] += n; T[i][1] = i; b[i] = 0; } else { T[i][0] += n; T[i][1] += n; b[i] = 0; } } for (int i = 0; i < n; i++) { int x = i, y = n; int cnt = 0; for (int itr = 1; itr <= 100000; itr++) { int g = a[x], h = b[y]; cnt += g != h; if (cnt > n) { assert(0); } x = S[x][h], y = T[y][g]; } } define_states(m, b, T, n); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...