Submission #1195329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195329		ByeWorld	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	7 ms	1608 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first 
#define se second
#define pb push_back
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;
const int MAXN = 3e5+100;
const ll INF = 2e18+10;
const int LOG = 12;

int n; 
vector<vector<int>> ANS;
vector<int> vec;

int cekbit(int n, int v){
	int p = 1;
	for(int i=0; i<v; i++) p *= 9;
	return (n/p)%9;
}
int type(int n, int v){
	return cekbit(n,v)/3;
}
std::vector<std::vector<int>> devise_strategy(int N) {
	n = N;
	// i = 0
	vec.pb(0);
	for(int j=1; j<=n; j++){
		vec.pb(24 - (type(j, 3)+6*(3)) );
	}
	ANS.pb(vec);
	int mx = -1;
	for(int i=1; i<=22; i++){ // di papan i
		int v = 24-i; int bit = v/6, num = v%6;
		vector<int> vec;
		if(bit == 0){
			// buka B trus cek aj
			vec.pb(1);
			for(int j=1; j<=n; j++){
				int ty = cekbit(j,bit);
				int nn = num;
				nn -= 2;
			// assert(num <= 4);
				nn *= 2;

				// kalo sama kan dari gede
				if(ty > nn) vec.pb(-1); // a lebih kecil
				else if(ty <= nn) vec.pb(-2); // a lebih gede
			}
			ANS.pb(vec);
			continue; 
		}
		if(num<=2){ // 0 1 2, group A nya
			// buka B
			vec.pb(1);
			for(int j=1; j<=n; j++){
				int ty = type(j,bit);
				if(ty < num) vec.pb(-2); // b lebih dikit
				else if(ty > num) vec.pb(-1); // a lebih dikit
				else {
					vec.pb(24 - (cekbit(j, bit)%3+6*bit+3) ); // +0 +1 +2
				}
			}
		} else { // buka A
			num -= 3;
			vec.pb(0);
			for(int j=1; j<=n; j++){
				if(cekbit(j,bit)%3 == num){ // kalo sama
					if(bit == 0) vec.pb(-1);
					else {
						if(bit==1){
							int nx = cekbit(j, bit-1); // ini nxnya
							if(nx == 8) vec.pb(-2); // a lebih gede
							else vec.pb(24 - (nx/2+2) );
						} else {
							vec.pb(24 - (type(j, bit-1)+6*(bit-1)) ); // kalo coin segini
						}
					}
				} else if(cekbit(j,bit)%3 > num){ // A lebih gede
					vec.pb(-2);
				} else {
					vec.pb(-1);
				}
			}
		}
		ANS.pb(vec);
		for(auto in : vec) mx = max(mx, in);
		// for(auto in : vec) cout << in << ' ';
		// 	cout << " in\n";
	}
// cout << mx << " mx\n";
	return ANS;
}

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