Submission #1230683

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

lockpicking

#include "lockpicking.h"
#include <bits/stdc++.h>
using namespace std;
void construct_card (int n, vector <int> a, vector <vector <int>> S) {
	vector <array <int, 2>> trie = {{-1, -1}};
	vector <int> node = {0};
	for (int i = 0; i < n; i++) {
		int x = i;
		vector <int> s;
		for (int j = 0; j < 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);
			}
			cur = trie[cur][j];
			node[cur] = x;
		}
	}
	//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) {
			T[i][0] = node[i - n];
			T[i][1] = 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;
		}
	}
	define_states(m, b, T, n);
}

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