Submission #782785

#	Time	Username	Problem	Language	Result	Execution time	Memory
782785		Tekor	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	9 ms	1456 KiB

prison

#include "prison.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define en '\n'
const int M = 30;
const int N = 5e3 + 10;
int a[M][N],k;
void build(int step,int type,int l,int r) {
	if(l > r)return;
	int pos = step * 3 - type;
	k = max(k,pos);
	a[pos][0] = step % 2;
	//cout << pos << " " << type << " " << l << " " << r << en;
	if(l == r) {
		a[pos][l] = -1;
		return;
	}
	int w1 = 0,w2 = 0;
	if(step % 2 == 0) {
		a[pos][l] = -1;
		a[pos][r] = -2;
		w1 = -1;
		w2 = -2;
	}else {
		a[pos][l] = -2;
		a[pos][r] = -1;
		w1 = -2;
		w2 = -1;
	}
	l++;
	r--;
	if(l > r)return;
	int sz = r - l + 1;
	int sz1 = sz / 3,sz2 = sz / 3,sz3 = sz / 3;
	if(sz % 3 >= 1)sz1++;
	if(sz % 3 == 2)sz2++;
	int pos1 = (step + 1) * 3 - 2,pos2 = (step + 1) * 3 - 1,pos3 = (step + 1) * 3;
	if(sz == 2) {
		sz1 = 2;
		sz2 = 0;
	}else if(sz == 3) {
		sz1 = 2;
		sz2 = 1;
		sz3 = 0;
	}else if(sz == 4) {
		sz1 = 2;
		sz2 = 2;
		sz3 = 0;
	}
	a[pos1][l - 1] = w2;
	a[pos1][r + 1] = w1;
	if(sz2 > 0) {
		a[pos2][l - 1] = w2;
		a[pos2][r + 1] = w1;
	}
	if(sz3 > 0) {
		a[pos3][l - 1] = w2;
		a[pos3][r + 1] = w1;
	}
	for(int i = l;i <= l + sz1 - 1;i++) {
		a[pos][i] = (step + 1) * 3 - 2;
		a[pos2][i] = w2;
		a[pos3][i] = w2;
	} 
	for(int i = l + sz1;i <= l + sz1 + sz2 - 1;i++) {
		a[pos][i] = (step + 1) * 3 - 1;
		a[pos1][i] = w1;
		a[pos3][i] = w2;
	}
	for(int i = l + sz1 + sz2;i <= r;i++) {
		a[pos][i] = (step + 1) * 3;
		a[pos1][i] = w1;
		a[pos2][i] = w1;
	}
	build(step + 1,2,l,l + sz1 - 1);
	if(sz2)build(step + 1,1,l + sz1,l + sz1 + sz2 - 1);
	if(sz3)build(step + 1,0,l + sz1 + sz2,r);
}

vector< vector<int> > devise_strategy(int n) {
	build(0,0,1,n);
	vector <vector <int> > ans;
	//cout << k << en;
	for(int i = 0;i <= k;i++) {
		vector <int> tek;
		for(int j = 0;j <= n;j++) {
			tek.pb(a[i][j]);
			//cout << a[i][j] << " ";
			assert(a[i][j] <= k);
		}
		//cout << en;
		ans.pb(tek);
	}
	return ans;
}

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