Submission #629139

#	Time	Username	Problem	Language	Result	Execution time	Memory
629139		handlename	Prisoner Challenge (IOI22_prison)	C++17	56 / 100	23 ms	1196 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
#define pb push_back
#define mp make_pair
int conv(int id){
	if (id==0) return -1;
	return -2;
}
int numbitt(int x){
	int res=0;
	while (x>0){
		x/=2;
		res++;
	}
	return res;
}
vector<vector<int> > devise_strategy(int n){
	int numbit=numbitt(n);
	vector<vector<int> > ans(numbit*2+1,vector<int>(n+1,0));
	ans[0][0]=0;
	for (int j=1;j<=n;j++){
		if (j&(1<<(numbit-1))) ans[0][j]=2;
		else ans[0][j]=1;
	}
	for (int i=1;i<(int)ans.size();i++){
		int lol=(i+1)/2;
		if (lol%2==0) ans[i][0]=0;
		else ans[i][0]=1;
		int bit=numbit-lol;
		for (int j=1;j<=n;j++){
			if (i%2==1 && j&(1<<bit)){
				ans[i][j]=conv(1-ans[i][0]);
			}
			else if (i%2==0 && !(j&(1<<bit))){
				ans[i][j]=conv(ans[i][0]);
			}
			else {
				if (bit==0){
					ans[i][j]=0;
					continue;
				}
				if (j&(1<<(bit-1))){
					ans[i][j]=lol*2+2;
				}
				else {
					ans[i][j]=lol*2+1;
				}
			}
		}
	}
	return ans;
}

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