Submission #825449

#	Time	Username	Problem	Language	Result	Execution time	Memory
825449		esomer	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1492 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"

using namespace std;

typedef long long ll;

int N;
vector<vector<int>> ans, inds;
vector<int> dp, which, sizes;
vector<vector<pair<int, int>>> ranges;

void calc_dp(){
	dp.assign(N+1, 1e9);
	which.assign(N+1, 1);
	for(int i = 0; i <= N; i++){
		int real = i - 2;
		if(real <= 0) dp[i] = 0;
		else{
			for(int x = 1; x <= 20; x++){
				int cll = real / x;
				if(real % x != 0) cll++;
				int needed = x + dp[cll]; 
				if(needed < dp[i]){
					which[i] = x;
					dp[i] = needed;
				}
			}
		}
	}
}

int get_groups(int i, vector<vector<pair<int, int>>>& ranges){
	pair<int, int> pr = ranges[i][0];
	int curr = 0;
	int groups = 0;
	for(int j = pr.first + 1; j < pr.second; j++) {
		curr++;
		if(curr == sizes[i + 1] || j == pr.second - 1) {
			groups++;
			curr = 0;
		}
	}
	return groups;
}

vector<vector<int>> devise_strategy(int n) {
	N = n;
	calc_dp();
	int total = N;
	while(total > 2){
		sizes.push_back(total);
		int x = which[total]; total -= 2;
		int nw = total / x;
		if(total % x != 0) nw++;
		total = nw;
	}
	sizes.push_back(total);
	ranges.assign((int)sizes.size(), {});
	inds.assign((int)sizes.size(), {});
	ranges[0].push_back({1, N});
	inds[0].push_back(0);
	ans.assign(21, vector<int>(N+1, 0));
	vector<int> col(N + 1, 0);
	int curr_ind = 1;
	for(int i = 0; i < (int)sizes.size(); i++){
		if(i == (int)sizes.size() - 1){
			for(int ind : inds[i]){
				for(pair<int, int> pr : ranges[i]){
					if(col[pr.first] == ind){
						ans[ind][pr.first] = -(ans[ind][0] + 1);
						ans[ind][pr.second] = -((1 - ans[ind][0]) + 1);
						if(pr.first > 1) ans[ind][pr.first - 1] = -(ans[ind][0] + 1);
						if(pr.second < N) ans[ind][pr.second + 1] = -((1 - ans[ind][0]) + 1);
					}else{
						for(int j = pr.first; j <= pr.second; j++) {
							if(col[j] > ind) {
								ans[ind][j] = -(ans[ind][0] + 1);
							}else{
								ans[ind][j] = -((1 - ans[ind][0]) + 1);
							}
						}
					}
				}
			}
			// cout << "i " << i << " sizes "<< sizes[i] << endl;
			// cout << "INDS: ";
			// for(int x : inds[i]) cout << x << " "; cout << endl;
			// cout << "Ranges: ";
			// for(pair<int, int> pr : ranges[i]) cout << pr.first << " " << pr.second << endl;
			// cout << "Col: ";
			// for(int x : col) cout << x << " "; cout << endl;
			continue;
		}
		int groups = get_groups(i, ranges);
		for(int j = 0; j < groups; j++){
			ans[curr_ind][0] = 1 - ans[inds[i][0]][0];
			inds[i+1].push_back(curr_ind); curr_ind++;
		}
		vector<int> nwcol(N+1, 0);
		for(int ind : inds[i]){
			for(pair<int, int> pr : ranges[i]){
				if(col[pr.first] == ind){
					ans[ind][pr.first] = -(ans[ind][0] + 1);
					ans[ind][pr.second] = -((1 - ans[ind][0]) + 1);
					if(pr.first > 1) ans[ind][pr.first - 1] = -(ans[ind][0] + 1);
					if(pr.second < N) ans[ind][pr.second + 1] = -((1 - ans[ind][0]) + 1);
					int curr = 0;
					int cind = 0;
					int lst = pr.first + 1;
					for(int j = pr.first + 1; j < pr.second; j++) {
						curr++;
						ans[ind][j] = inds[i + 1][cind];
						nwcol[j] = inds[i + 1][cind];
						if(curr == sizes[i + 1] || j == pr.second - 1) {
							ranges[i+1].push_back({lst, j});
							curr = 0; cind++; lst = j + 1;
						}
					}
				}else{
					for(int j = pr.first; j <= pr.second; j++) {
						if(col[j] < ind) {
							ans[ind][j] = -(ans[ind][0] + 1);
							if(pr.first > 1) ans[ind][pr.first - 1] = -(ans[ind][0] + 1);
							if(pr.second < N) ans[ind][pr.second + 1] = -(ans[ind][0] + 1);
						}else{
							ans[ind][j] = -((1 - ans[ind][0]) + 1);
							if(pr.first > 1) ans[ind][pr.first - 1] = -((1 - ans[ind][0]) + 1);
							if(pr.second < N) ans[ind][pr.second + 1] = -((1 - ans[ind][0]) + 1);
						}
					}
				}
			}
		}
		col = nwcol;
		// cout << "i " << i << " sizes "<< sizes[i] << endl;
		// cout << "INDS: ";
		// for(int x : inds[i]) cout << x << " "; cout << endl;
		// cout << "Ranges: ";
		// for(pair<int, int> pr : ranges[i]) cout << pr.first << " " << pr.second << endl;
		// cout << "Col: ";
		// for(int x : col) cout << x << " "; cout << endl;
	}
	// cout << "ANS" << endl;
	// for(int i = 0; i < 5; i++){
	// 	cout << "I: " << i << endl;
	// 	for(int x : ans[i]) cout << x << " "; cout << endl;
	// }
	return ans;
}

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