oj.uz

Submission #842626

# Submission time Handle Problem Language Result Execution time Memory
842626 2023-09-03T06:26:18 Z WLZ Lockpicking (IOI23_lockpicking) C++17
100 / 100
 172 ms 3272 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
2 Correct 1 ms 348 KB ok, most errors: 0 (allowed: 1)
3 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
4 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
5 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
6 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
7 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
8 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
9 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
10 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
11 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
12 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 348 KB ok, most errors: 5 (allowed: 29)
2 Correct 10 ms 348 KB ok, most errors: 4 (allowed: 29)
3 Correct 9 ms 436 KB ok, most errors: 3 (allowed: 29)
4 Correct 9 ms 348 KB ok, most errors: 4 (allowed: 29)
5 Correct 12 ms 348 KB ok, most errors: 6 (allowed: 29)
6 Correct 9 ms 436 KB ok, most errors: 6 (allowed: 29)
7 Correct 9 ms 348 KB ok, most errors: 6 (allowed: 29)
8 Correct 9 ms 348 KB ok, most errors: 4 (allowed: 29)

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB ok, most errors: 3 (allowed: 899)
2 Correct 8 ms 348 KB ok, most errors: 4 (allowed: 899)
3 Correct 9 ms 436 KB ok, most errors: 10 (allowed: 899)
4 Correct 9 ms 348 KB ok, most errors: 4 (allowed: 899)
5 Correct 9 ms 348 KB ok, most errors: 6 (allowed: 899)
6 Correct 10 ms 348 KB ok, most errors: 7 (allowed: 899)
7 Correct 9 ms 348 KB ok, most errors: 7 (allowed: 899)
8 Correct 11 ms 348 KB ok, most errors: 4 (allowed: 899)

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
2 Correct 1 ms 348 KB ok, most errors: 0 (allowed: 1)
3 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
4 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
5 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
6 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
7 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
8 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
9 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
10 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
11 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
12 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
13 Correct 11 ms 348 KB ok, most errors: 5 (allowed: 29)
14 Correct 10 ms 348 KB ok, most errors: 4 (allowed: 29)
15 Correct 9 ms 436 KB ok, most errors: 3 (allowed: 29)
16 Correct 9 ms 348 KB ok, most errors: 4 (allowed: 29)
17 Correct 12 ms 348 KB ok, most errors: 6 (allowed: 29)
18 Correct 9 ms 436 KB ok, most errors: 6 (allowed: 29)
19 Correct 9 ms 348 KB ok, most errors: 6 (allowed: 29)
20 Correct 9 ms 348 KB ok, most errors: 4 (allowed: 29)
21 Correct 90 ms 1200 KB ok, most errors: 7 (allowed: 127)
22 Correct 142 ms 3272 KB ok, most errors: 23 (allowed: 149)
23 Correct 151 ms 2752 KB ok, most errors: 13 (allowed: 149)
24 Correct 134 ms 2244 KB ok, most errors: 16 (allowed: 149)
25 Correct 137 ms 1740 KB ok, most errors: 10 (allowed: 149)
26 Correct 172 ms 1760 KB ok, most errors: 11 (allowed: 149)
27 Correct 147 ms 1876 KB ok, most errors: 9 (allowed: 149)
28 Correct 136 ms 1740 KB ok, most errors: 9 (allowed: 149)
29 Correct 133 ms 1732 KB ok, most errors: 10 (allowed: 149)
30 Correct 144 ms 1740 KB ok, most errors: 9 (allowed: 149)
31 Correct 142 ms 1740 KB ok, most errors: 8 (allowed: 149)
32 Correct 140 ms 1876 KB ok, most errors: 9 (allowed: 149)