Submission #732164

#	Time	Username	Problem	Language	Result	Execution time	Memory
732164		ismayil	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	17 ms	1108 KiB

prison

#pragma GCC optimize("O3")
#include "prison.h"
#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> devise_strategy(int N) {
	vector<vector<int>> s(25, vector<int>(N + 1, 0));
	s[0][0] = 0;
	for(int i = 1; i <= N; i++) s[0][i] = ((i & (1 << 12)) ? 2 : 1);
	for(int i = 1; i <= 24; i++){
		int d = (i - 1) / 2;
		int bit = (i - 1) % 2;
		if(d % 2 == 0) s[i][0] = 1;
		else s[i][0] = 0;
		for(int j = 1; j <= N; j++){
			int _bit = __builtin_popcount((j & (1<<(12 - d))));
			if(bit < _bit){
				if(d % 2 == 0) s[i][j] = -1;
				else s[i][j] = -2;
			}else if(bit > _bit){
				if(d % 2 == 0) s[i][j] = -2;
				else s[i][j] = -1;
			}else{
				if(i == 23 || i == 24){
					if(j & (1<<(11 - d))) s[i][j] = -2;
					else s[i][j] = -1;
				}
				else s[i][j] = (d + 1) * 2 + 1 + __builtin_popcount((j & (1<<(11 - d))));
			}
		}
	}
	return s;
}

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