Submission #739300

#	Time	Username	Problem	Language	Result	Execution time	Memory
739300		sentheta	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1364 KiB

prison

#include "prison.h"
#include<iostream>
#include<cassert>
#include<algorithm>
#include<vector>
#include<array>
#include<utility>
#include<set>
#include<map>
#include<string>
#include<random>
using namespace std;

#define pii pair<int,int>
#define V vector
#define rep(i,a,b) for(int i=a; i<(int)b; i++)
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define nl '\n'
#define _ << " " << 
#define ff first
#define ss second

V<V<int>> g;

void dnc(int l,int r,int i,int who){
	if(l > r) return;
	g[i][0] = who;
	
	int nxt = i;
	while(nxt%3) nxt++;

	V<pii> lr;
	if(nxt==18){ // split two
		int m = (l+r)/2;
		if(l+1<=m) lr.push_back({l+1,m});
		if(m+1<=r-1) lr.push_back({m+1,r-1});
	}
	else{ // split three
		int m1 = (2*l+r)/3, m2 = (l+2*r)/3;
		if(l+1<=m1) lr.push_back({l+1,m1});
		if(m1+1<=m2) lr.push_back({m1+1,m2});
		if(m2+1<=r-1) lr.push_back({m2+1,r-1});
	}

	for(int x=l; x<=r; x++){
		if(x==l) g[i][x] = (who?-2:-1);
		else if(x==r) g[i][x] = (who?-1:-2);
		else{
			rep(j,0,lr.size()) if(lr[j].ff<=x && x<=lr[j].ss){
				g[i][x] = nxt+j+1;
			}
		}
	}

	rep(j,0,lr.size()){
		auto[tl,tr] = lr[j];

		for(int x=l; x<=tl-1; x++) g[nxt+j+1][x] = (who?-1:-2);
		for(int x=tr+1; x<=r; x++) g[nxt+j+1][x] = (who?-2:-1);

		dnc(tl,tr, nxt+j+1, who^1);
	}
}

V<V<int>> devise_strategy(int N) {
	g = V<V<int>>(21,V<int>(N+1));
	dnc(1,N,0,0);
	return g;
}

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