Submission #739244

#	Time	Username	Problem	Language	Result	Execution time	Memory
739244		sentheta	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	1588 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<b; i++)
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define nl '\n'
#define _ << " " << 

const int K = 20;
V<V<int>> g;

V<pii> lr[K+1];

V<V<int>> devise_strategy(int N) {
	g = V<V<int>>(2*K+3,V<int>(N+1));

	lr[0].push_back({1,N});
	for(int i=0; i<=K; i++) if(!lr[i].empty()){
		// dbg(i);
		// dbg(lr[i].size());

		for(auto[l,r] : lr[i]){
			// cout << l _ r << nl;

			if(l+1 <= r-1){
				int m = (l+r)/2;
				if(l+1<=m) lr[i+1].push_back({l+1,m});
				if(m+1<=r-1) lr[i+1].push_back({m+1,r-1});
				
				// dbg(m);
			}
		}
		// cout << nl;
	}

	// lvl 0
	g[0][0] = 0;
	g[0][1] = -1;
	g[0][N] = -2;
	for(int x=2; x<=N-1; x++){
		int m = (N+1)/2;
		if(x<=m) g[0][x] = 1;
		else g[0][x] = 2;
	}

	for(int i=1; i<=2*K+2; i++){
		int p = (i-1)/2, q = p+1;
		g[i][0] = 0;
		int thiss = -1, thatt = -2;
		if(q%2){
			g[i][0] ^= 1;
			swap(thiss, thatt);
		}

		for(auto[l,r] : lr[p]) for(int x=l; x<=r; x++){
			// l++; r--;
			int m = (l+r)/2;

			if(x<=l) g[i][x] = thiss;
			else if(r<=x) g[i][x] = thatt;
			
			// thiss is leftchild
			else if(l+1<=x && x<=m){
				// thatt is leftchild
				if(i%2){
					if(x==l+1) g[i][x] = thiss;
					else if(x==m) g[i][x] = thatt;
					else if(x <= (l+1+m)/2) g[i][x] = 2*q+1;
					else g[i][x] = 2*q+2;
				}
				// thatt is rightchild
				else g[i][x] = thiss;
			}

			// thiss is rightchild
			else if(m+1<=x && x<=r-1){
				// thatt is leftchild
				if(i%2) g[i][x] = thatt;
				// thatt is rightchild
				else{
					if(x==m+1) g[i][x] = thiss;
					else if(x==r-1) g[i][x] = thatt;
					else if(x <= (m+1+r-1)/2) g[i][x] = 2*q+1;
					else g[i][x] = 2*q+2;
				}
			}
		
			// l--; r++;
		}
	}

	V<int> zro = V<int>(N+1), one = zro;
	one[0] = 1;
	while(g.back()==zro || g.back()==one) g.pop_back();
	for(V<int>&v : g){
		for(int&x : v){
			// if(x > g.size()-1) x = 0;
			// cout << x << " ";
		}
		// cout << nl;
	}
	g.pop_back();
	g.pop_back();
	// dbg(g.size());

	return g;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:108:11: warning: unused variable 'x' [-Wunused-variable]
  108 |   for(int&x : v){
      |           ^

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