Submission #1231171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231171		chaeryeong	Lockpicking (IOI23_lockpicking)	C++20	0 / 100	955 ms	440 KiB

lockpicking

#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 <= 10000000; 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);
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 30
• Subtask 3: 0 / 20
• Subtask 4: 0 / 29