Submission #625758

#	Time	Username	Problem	Language	Result	Execution time	Memory
625758		sofapuden	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	10 ms	1492 KiB

prison

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

using namespace std;

vector<vector<int>> ans;
int n;

void fin(int l, int r, int i){
	int z = (i+2)/3;
	int box = ((i+2)%6 < 3);
	ans[i][l] = ~box;
	ans[i][r] = ~(int)(!box);
	l++;
	r--;
	if(l > r)return;
	ans[z*3+1][l-1] = ans[z*3+2][l-1] = ans[z*3+3][l-1] = ~(int)(!box);
	ans[z*3+1][r+1] = ans[z*3+2][r+1] = ans[z*3+3][r+1] = ~box;
	int d1 = l+(r-l)/3, d2 = r - (r-l)/3;
	for(int j = l; j <= d1; ++j){ans[i][j] = z*3+1;ans[z*3+2][j] = ans[z*3+3][j] = ~(int)(!box);}
	for(int j = d1+1; j <= d2; ++j){ans[i][j] = z*3+2;ans[z*3+1][j] = ~box; ans[z*3+3][j] = ~(int)(!box);}
	for(int j = d2+1; j <= r; ++j){ans[i][j] = z*3+3; ans[z*3+1][j] = ans[z*3+2][j] = ~box;}
	fin(l,d1,z*3+1);
	fin(d1+1,d2,z*3+2);
	fin(d2+1,r,z*3+3);
}

vector<vector<int>> devise_strategy(int N) {
	n = N;
	ans.resize(22,vector<int>(N+1,0));
	for(int i = 0; i < 22; ++i)ans[i][0] = ((i+2)%6 < 3);
	fin(1,N,0);
	return ans;
}

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