Submission #842626

#	Time	Username	Problem	Language	Result	Execution time	Memory
842626		WLZ	Lockpicking (IOI23_lockpicking)	C++17	100 / 100	172 ms	3272 KiB

lockpicking

#include "lockpicking.h"
#include <bits/stdc++.h>
using namespace std;

void construct_card(int n, std::vector<int> a, std::vector<std::vector<int>> s) {
	srand(time(nullptr));
	vector<int> b = a; vector< vector<int> > t = s;
	vector<int> seq(n, 0); int best = 0;
	for (int k = 0; k < 1000; k++) {
		vector<int> new_seq(n, 0);
		for (int i = 0; i < n; i++) new_seq[i] = rand() % 2;
		set<string> st;
		for (int i = 0; i < n; i++) {
			string tmp(1, a[i] + '0');
			for (int l = 0, cur = s[i][new_seq[0]]; l < n; l++) {
				tmp += a[cur] + '0';
				cur = s[cur][new_seq[(l + 1) % n]];
			}
			st.insert(tmp);
		}
		if ((int) st.size() >= best) {
			best = (int) st.size();
			seq = new_seq;
		}
	}
	//for (auto &x : seq) cerr << x << ' ';
	//cerr << endl;
	vector< vector< vector< pair<int, int> > > > potential = {{}};
	for (int i = 0; i < n; i++) {
		vector< pair<int, int> > tmp = {{a[i], i}};
		int j = s[i][seq[0]];
		for (int k = 0; k < n; k++) {
			tmp.push_back({a[j], j});
			j = s[j][seq[(k + 1) % n]];
		}
		reverse(tmp.begin(), tmp.end());
		potential[0].push_back(tmp);
	}
	for (int i = 0; i < (int) potential.size(); i++) {
		t.push_back({0, 0});
		b.push_back(seq[n - (int) potential[i].back().size() + 1]);
		vector< vector< pair<int, int> > > zero, one;
		for (auto &v : potential[i]) {
			if (v.back().first == 0) zero.push_back(v);
			else one.push_back(v);
		}
		set< vector<int> > st_0, st_1;
		for (auto &v : zero) {
			v.pop_back();
			vector<int> tmp;
			for (auto &p : v) tmp.push_back(p.first);
			st_0.insert(tmp);
		}
		for (auto &v : one) {
			v.pop_back();
			vector<int> tmp;
			for (auto &p : v) tmp.push_back(p.first);
			st_1.insert(tmp);
		}
		if ((int) st_0.size() == 1) t[i + n][0] = zero.back().back().second;
		else if (!st_0.empty()) {
			t[i + n][0] = (int) potential.size() + n;
			potential.push_back(zero);
		}
		if ((int) st_1.size() == 1) t[i + n][1] = one.back().back().second;
		else if (!st_1.empty()) {
			t[i + n][1] = (int) potential.size() + n;
			potential.push_back(one);
		}
	}
	define_states((int) b.size(), b, t, n);
}

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