Submission #732195

#	Time	Username	Problem	Language	Result	Execution time	Memory
732195		ismayil	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	33 ms	1052 KiB

prison

#pragma GCC optimize("O3")
#include "prison.h"
#include<bits/stdc++.h>
using namespace std;
int get_bit(int n, int idx){
	vector<int> bits;
	for(int i = 0; i <= 7; i++){
		bits.push_back(n % 3);
		n /= 3;
	}
	reverse(bits.begin(), bits.end());
	return bits[idx];
}
vector<vector<int>> devise_strategy(int N) {
	vector<vector<int>> s(23, vector<int>(N + 1, 0));
	s[0][0] = 0;
	for(int i = 1; i <= N; i++) s[0][i] = get_bit(i, 0) + 1;
	for(int i = 1; i <= 22; i++){
		int d = (i - 1) / 3;
		int bit = (i - 1) % 3;
		if(d % 2 == 0) s[i][0] = 1;
		else s[i][0] = 0;
		for(int j = 1; j <= N; j++){
			int _bit = get_bit(j, d);
			if(i == 22){
				if(_bit > 1) s[i][j] = -2;
				else s[i][j] = -1;
			}
			else 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(d == 6){
					if(get_bit(j, d + 1) == 0) s[i][j] = -2;
					else if(get_bit(j, d + 1) == 1) s[i][j] = 22;
					else s[i][j] = -1;
				}
				else s[i][j] = (d + 1) * 3 + 1 + get_bit(j, d + 1);
			}
		}
	}
	return s;
}

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