Submission #1044832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044832		Dan4Life	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	348 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
const int mxN = (int)1e5+10;
const ll LINF = (ll)2e18;
const int mxX = 25;
int pow2[20];

vector<vi> devise_strategy(int N) {
	pow2[0] = 1;
	for(int i = 1; i < 20; i++) pow2[i]=pow2[i-1]*2;
	vector<vi> ans(mxX+1,vi(N+1,0));
	int fi = 1, cur = 0;
	ans[0][0] = 0; // if we are at 0, inspect A.
	for(int i = 1; i <= N; i++) 
		ans[0][i] = 1+i/pow2[12];
		
	for(int i = 12; i>=0; i--){
		cur^=1;
		
		for(int j = fi; j <= fi+1; j++){
			ans[j][0] = cur;
			for(int k = 1; k <= N; k++){
				int curA=(k%pow2[i+1])/pow2[i], curB = j-fi;
				if(cur) swap(curA,curB);
				if(curA<curB) ans[j][k]=-1;
				else if(curA>curB) ans[j][k]=-2;
				else if(i) ans[j][k] = fi+2+(k%pow2[i])/pow2[i-1];
			}
		}
		fi+=2;
	}
	return ans;
}

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