Submission #866526

#	Time	Username	Problem	Language	Result	Execution time	Memory
866526		vjudge1	Prisoner Challenge (IOI22_prison)	C++17	60 / 100	10 ms	1116 KiB

prison

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

vector<vector<int>> devise_strategy(int N) {
	vector<vector<int>> s(26, vector<int>(N+1, 0));;
	s[0][0] = 0;// inspect A

	for (int i = 0, h=12; i <= 12; i++, h--){
		for (int b = 0; b < 2; b++){
			int val = (i<<1)+b;// the value of the hash
			// if odd I will inspect b
			// else I will inspect a
			s[val][0] = (i&1);
			for (int k = 1; k <= N; k++){
				int o[2];
				o[0] = ((k>>(h+1)) & 1);
				o[1] = ((k>>h) & 1);
				if (b != o[0]){
					if (i&1){
						if (b > o[0]) s[val][k] = -2;
						else s[val][k] = -1;
					}
					else {
						if (b > o[0]) s[val][k] = -1;
						else s[val][k] = -2;
					}
				}
				else {
					if (i==12){
						if (o[1]==1) s[val][k] = -2;
						else s[val][k] = -1;
					}
					else s[val][k] = ((i+1)<<1)+o[1];
				}
			}
		}
	}
	// i = 12
	return s;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 50 / 90