Submission #880577

#	Time	Username	Problem	Language	Result	Execution time	Memory
880577		42kangaroo	Lockpicking (IOI23_lockpicking)	C++17	100 / 100	1 ms	596 KiB

lockpicking

#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 (stderr)

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 / 21
• Subtask 2: 30 / 30
• Subtask 3: 20 / 20
• Subtask 4: 29 / 29