Submission #1229599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229599		clemmy14	Prisoner Challenge (IOI22_prison)	C++20	38 / 100	16 ms	1608 KiB

prison

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

bool cal(int val, int i) {
	int cur=1, tar=1;
	while(cur<val) cur*=2;
	while(i--) tar*=2;
	while(val != 0) {
		if(val >= cur) {
			val-=cur;
			if(cur == tar) return true;
		}
		cur/=2;
	}
	return false;
}

vector<vector<int>> devise_strategy(int N) {
	int larP=0, idx=1;
	while(N >= idx) {
		idx*=2; larP++;
	}
	vector<vector<int>> s(larP*3, vector<int>(N+1, 0));
	for(int i=larP; i<larP*3; i++) s[i][0]=1;
	for(int i=0; i<larP*3; i++) {
		int pow = (larP-1)-(i%larP);
		if(i < larP) {
			for(int j=1; j<=N; j++) {
				if(cal(j, pow)) s[i][j]=i+larP*2;
				else s[i][j]=i+larP;
			}
		} else if(i < larP*2) {
			for(int j=1; j<=N; j++) {
				if(cal(j, pow)) s[i][j]=-1;
				else s[i][j]=i-larP+1;
			}
		} else {
			for(int j=1; j<=N; j++) {
				if(cal(j, pow)) s[i][j]=i-larP*2+1;
				else s[i][j]=-2;
			}
		}
	}
	return s;
}

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