Submission #626403

#	Time	Username	Problem	Language	Result	Execution time	Memory
626403		Mr_Husanboy	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	12 ms	2016 KiB

prison

#include "prison.h"

#include <vector>

#include<bits/stdc++.h>




using namespace std;
using ll = long long;



mt19937 rng(123);
#define ld long double
#define ull unsigned long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define setp(x) setprecision(x)



int old(int n){
	int k = 31 - __builtin_clz(n);
	if(__builtin_popcount(n) == 1) k--;
	return k;
}




#define a -1
#define b -2


vector<vector<int>> devise_strategy(int n) {
	vector<vi> res;
	if(n == 2){
		return {{0,a,b}};
	}
	int n2 = old(n); 
	res.assign((n2 + 1)*2+1, vi((1<<(n2 + 1)) + 1,0));
	int x = res.size(), sz = res[0].size();
	for(int i = 1; i < sz; i ++){
		if((i-1) & (1 << n2)) res[0][i] = 2;
		else res[0][i] = 1;
//		cout << res[0][i] << endl;
	}
	int l = 3, r = 4;
	for(int i = 1; i < x; i +=2){
		if(i%4 == 1) res[i][0] = res[i + 1][0] = 1;
		if(res[i][0] == 1){
	//		cout << i << ' ' << i+1 << endl;
			for(int j = 1; j < sz; j ++){
				if((j-1)&(1 << n2)){
					res[i][j] = a;
					if((j-1)&(1 << (n2 - 1))){
						res[i + 1][j] = r;
					}else res[i + 1][j] = l;
				}else{
					res[i + 1][j] = b;
					if((j-1)&(1 << (n2 - 1))){
						res[i][j] = r;
					}else res[i][j] = l;
				}
			}
		}else{
			for(int j = 1; j < sz; j ++){
				if((j-1)&(1 << n2)){
					res[i][j] = b;
					if((j-1)&(1 << (n2 - 1))){
						res[i + 1][j] = r;
					}else res[i + 1][j] = l;
				}else{
					res[i + 1][j] = a;
					if((j-1)&(1 << ( n2 - 1))){
						res[i][j] = r;
					}else res[i][j] = l;
				}
			}
		}
		l += 2; r += 2;
		n2 --;
	}
	vector<vi> ans(x - 2, vi(n + 1, -10));
	for(int i = 0; i < x - 4; i ++){
		for(int j = 0; j <= n; j ++){
			ans[i][j] = res[i][j];
		}
	}
	r -= 2, l -= 2;
	for(int j = x - 4; j < x - 2; j ++){
		ans[j][0] = res[j][0];
		for(int i = 1; i <= n; i ++){
			if(res[j][i] > 0){
				if(i%2 == 1){
					ans[j][i] = (res[j][0] == 0? a : b);
				}else{
					ans[j][i] = (res[j][0] == 0? b : a);
				}
			}else ans[j][i] = res[j][i];
		}
	}
	
/*	for(int i = 0; i < x; i ++){
		for(int j = 0; j < sz; j ++){
			if(res[i][j] >= 0) cout << res[i][j] << ' ';
			else cout << char(-res[i][j] + 'a' - 1) << ' ';
		} cout << endl;
	}*/
	return ans;
}

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