Submission #1240078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240078		nikulid	죄수들의 도전 (IOI22_prison)	C++20	65 / 100	7 ms	1096 KiB

prison

#include "prison.h"
#include <assert.h>
#include <vector>
#include <iostream>

using namespace std;
bool debug=0;

#define derr if(debug)cerr
#define pb push_back

vector<vector<int>> devise_strategy(int N) {
	vector<vector<int>> answer;
	vector<int> cur(N+1,0);
	int ri;
	
	cur[0]=0; // inspect box A!
	for(int i=1; i<N+1; i++){
		if(i <= 4096){
			cur[i] = 1;
		} else{
			cur[i] = 2;
		}
	}
	answer.pb(cur);


	bool lastbox = 0;

	int pmod = 8192;
	int mod = 4096;
	int nexti = 1;

	while(pmod>4){
		/*
		basically zoom in:
		
		1       m     p    1             m
		|---I---|--I--| => |---I---|--I--|
					   M     P
		*/
		
		nexti += 2;

		cur[0] = !lastbox;
		// lastbox was in lower region
		for(int i=1; i<N+1; i++){
			ri = ((i-1)%pmod)+1;
			if(ri <= mod){ // same zone
				if(((ri-1)%mod)+1 <= mod/2){
					cur[i] = nexti;
				} else{
					cur[i] = nexti+1;
				}
			} else{ // this box is greater.
				cur[i] = ((lastbox+1)*-1);
			}
		}
		answer.pb(cur);
		// lastbox was in higher region
		for(int i=1; i<N+1; i++){
			ri = ((i-1)%pmod)+1;
			if(ri <= mod){ // this box is lesser
				cur[i] = ((!lastbox+1)*-1);
			} else{ // same zone
				if(((ri-1)%mod)+1 <= mod/2){
					cur[i] = nexti;
				} else{
					cur[i] = nexti+1;
				}			
			}
		}
		answer.pb(cur);
		
		lastbox = !lastbox;
		pmod/=2;
		mod/=2;

	} 
	// pmod=4, mod=2
	
	// now we must explore box A.
	cur[0] = 0;
	// (24) valB is in the lower zone (1-2 MOD 4)
	for(int i=1; i<N+1; i++){
		ri = ((i-1)%pmod)+1;
		if(ri>1) cur[i]=-2;
		else cur[i]=-1;
	}
	answer.pb(cur);
	// (25) valB in the upper zone (3-4 MOD 4)
	for(int i=1; i<N+1; i++){
		ri = ((i-1)%pmod)+1;
		if(ri<4) cur[i]=-1;
		else cur[i]=-2; // <-- !
	}
	answer.pb(cur);

	derr<<"answer.size() >> "<<answer.size()<<"\n";
	derr<<"previous box: "<<lastbox<<"\n";
	derr<<"we know the answer %"<<pmod<<" is between 1 "<<mod<<"\n";
	return answer;
}

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