Submission #629623

#	Time	Username	Problem	Language	Result	Execution time	Memory
629623		PoPularPlusPlus	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	70 ms	1048 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

int con(int x){
	if(x == 0)return -2;
	return -1;
}

std::vector<std::vector<int>> devise_strategy(int n) {
	vector<vector<int>> v(25);
	for(int i = 0; i < 25; i++)v[i].resize(n + 1);
	queue<int> q;
	q.push(0);
	while(q.size()){
		int i = q.front();
		q.pop();
		if(i == 0){
			v[i][0] = 0;
			for(int j = 1; j < n + 1; j++){
				if((j&(1 << (12))) > 0){
					v[i][j] = 12;
				}
				else v[i][j] = 24;
			}
			q.push(12);
			q.push(24);
		}
		else {
			if(i % 2 == 0)v[i][0] = 1;
			else v[i][0] = 0;
			int bit = i - 1;
			if(i > 12)bit -= 12;
			if(bit == 0){
				v[i][0] = 0;
				for(int j = 1; j < n + 1; j++){
					int set = 0;
					if((j & (1 << (bit+1))) > 0){
						set = 1;
					}
					int s = (i > 12 ? 0 : 1);
					if(s != set){
						if(set > s){
							v[i][j] = con(v[i][0]); 
						}
						else v[i][j] = con((v[i][0] + 1)%2);
					}
					else {
						if((j&(1 << bit)) > 0){
							v[i][j] = con(v[i][0]);
						}
						else v[i][j] = con((v[i][0] + 1)%2);
					}
				}
			}
			else {
				for(int j = 1; j < n + 1; j++){
					int set = 0;
					if((j & (1 << (bit+1))) > 0){
						set = 1;
					}
					int s = (i > 12 ? 0 : 1);
					if(s != set){
						if(set > s){
							v[i][j] = con(v[i][0]);
						}
						else v[i][j] = con((v[i][0] + 1)%2);
					}
					else {
						if((j&(1 << bit)) > 0){
							v[i][j] = bit;
						}
						else v[i][j] = bit + 12;
					}
				}
				q.push(bit);
				q.push(bit + 12);
			}
		}
	}
	return v;
}

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