oj.uz

Submission #880577

# Submission time Handle Problem Language Result Execution time Memory
880577 2023-11-29T16:58:04 Z 42kangaroo Lockpicking (IOI23_lockpicking) C++17
100 / 100
 1 ms 596 KB 
#include "lockpicking.h"
#include "bits/stdc++.h"

using namespace std;

struct Node {
	bitset<150> state, E0, E1;
	int B;
};

void construct_card(int N, std::vector<int> A, std::vector<std::vector<int>> S) {
	vector<Node> nodes;
	unordered_map<bitset<150>, int> had;
	queue<bitset<150>> q;
	//define start state
	bitset<150> st;
	for (int i = 0; i < N; ++i) {
		st.set(i);
	}
	had.insert({st, 0});
	q.push(st);
	// loop over all states in queue
	while (!q.empty()) {
		auto top = q.front();
		q.pop();
		nodes.push_back({top, bitset<150>(), bitset<150>(), -1});
		had[top] = nodes.size() - 1;
		// make B be the max of 1 or 0
		int num1 = 0;
		for (int i = 0; i < N; ++i) {
			num1 += (top[i] && A[i]);
		}
		nodes.back().B = num1 > top.count() / 2;
		// Check possible next states if 1 or 0
		for (int i = 0; i < N; ++i) {
			if (top[i]) {
				if (A[i]) {
					nodes.back().E1.set(S[i][nodes.back().B]);
				} else {
					nodes.back().E0.set(S[i][nodes.back().B]);
				}
			}
		}
		// add state to queue if it is not done yet, mark it as had
		if (had.find(nodes.back().E0) == had.end()) {
			had.insert({nodes.back().E0, -1});
			q.push(nodes.back().E0);
		}
		if (had.find(nodes.back().E1) == had.end()) {
			had.insert({nodes.back().E1, -1});
			q.push(nodes.back().E1);
		}
	}
	// convert to output format
	vector<int> B(nodes.size());
	vector<vector<int>> T(nodes.size(), vector<int>(2));
	for (int i = 0; i < nodes.size(); ++i) {
		B[i] = nodes[i].B;
		T[i][0] = had[nodes[i].E0];
		T[i][1] = had[nodes[i].E1];
	}
	define_states(nodes.size(), B, T, 0);
}

Compilation message

lockpicking.cpp: In function 'void construct_card(int, std::vector<int>, std::vector<std::vector<int> >)':
lockpicking.cpp:33:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   nodes.back().B = num1 > top.count() / 2;
      |                    ~~~~~^~~~~~~~~~~~~~~~~
lockpicking.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < nodes.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok, most errors: 1 (allowed: 1)
2 Correct 0 ms 588 KB ok, most errors: 0 (allowed: 1)
3 Correct 0 ms 596 KB ok, most errors: 0 (allowed: 1)
4 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
5 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
6 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
7 Correct 1 ms 344 KB ok, most errors: 1 (allowed: 1)
8 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
9 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
10 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
11 Correct 0 ms 344 KB ok, most errors: 1 (allowed: 1)
12 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
13 Correct 1 ms 348 KB ok, most errors: 2 (allowed: 29)
14 Correct 1 ms 344 KB ok, most errors: 3 (allowed: 29)
15 Correct 0 ms 348 KB ok, most errors: 3 (allowed: 29)
16 Correct 0 ms 348 KB ok, most errors: 3 (allowed: 29)
17 Correct 0 ms 348 KB ok, most errors: 4 (allowed: 29)
18 Correct 0 ms 348 KB ok, most errors: 3 (allowed: 29)
19 Correct 0 ms 348 KB ok, most errors: 4 (allowed: 29)
20 Correct 0 ms 348 KB ok, most errors: 4 (allowed: 29)
21 Correct 0 ms 344 KB ok, most errors: 5 (allowed: 127)
22 Correct 0 ms 348 KB ok, most errors: 4 (allowed: 149)
23 Correct 1 ms 412 KB ok, most errors: 4 (allowed: 149)
24 Correct 1 ms 348 KB ok, most errors: 4 (allowed: 149)
25 Correct 1 ms 348 KB ok, most errors: 5 (allowed: 149)
26 Correct 1 ms 348 KB ok, most errors: 6 (allowed: 149)
27 Correct 1 ms 344 KB ok, most errors: 5 (allowed: 149)
28 Correct 1 ms 348 KB ok, most errors: 6 (allowed: 149)
29 Correct 1 ms 392 KB ok, most errors: 5 (allowed: 149)
30 Correct 1 ms 344 KB ok, most errors: 5 (allowed: 149)
31 Correct 1 ms 348 KB ok, most errors: 5 (allowed: 149)
32 Correct 1 ms 348 KB ok, most errors: 5 (allowed: 149)