Submission #1239890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239890		nikulid	Prisoner Challenge (IOI22_prison)	C++20	38 / 100	11 ms	1608 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 digit;
	derr<<"process called!\n";
	// (0) A: THOUSAND's digit
	cur[0] = 0; // inspect bag A!
	cur[N] = -2; cur[1] = -1; // (edge cases)
	for(int i=2; i<N; i++){
		digit = i/1000;
		cur[i] = digit+1; // everything will be in the range {1:5} (inclusive). 
	}
	
	derr<<"right before first answer.pb(cur)... ";
	answer.pb(cur);
	derr<<"done :)\n";
	
	// (1-5) B: check thousand's digit
	for(int D=0; D<=4; D++){
		derr<<"$ D="<<D<<"\n";
		cur[0] = 1; // inspect bag B!
		cur[N] = -1; cur[1] = -2; // (edge cases)
		for(int i=2; i<N; i++){
			digit = i/1000;
			if(digit<D){
				cur[i] = -2;
			} else if(digit>D){
				cur[i] = -1;
			} else{
				cur[i] = 6;
			}
		}
		answer.pb(cur);
	}

	derr<<"(1-5) init complete!\n";
	derr<<"`answer` is now of size "<<answer.size()<<"\n";

	for(int i=6; i<=8; i++)answer.pb(vector<int>(N+1, 0));

	// (6-8) A: move on to the appropriate digit
	cur[0] = 0; // inspect bag A!
	for(int i=2; i<N; i++){
		digit = (i%1000)/100;
		answer[6][i] = 10 + digit;
		digit = (i%100)/10;
		answer[7][i] = 20 + digit;
		digit = (i%10);
		answer[8][i] = 30 + digit;
		if(answer[8][i]==39) answer[8][i]=9;
	}

	// (9) B: check one's digit
	int D=9;
	cur[0] = 1; // inspect bag B!
	for(int i=2; i<N; i++){
		digit = i%10;
		if(digit<D){
			cur[i] = -2;
		} else if(digit>D){ 
			cur[i] = -1;
		} else{
			cur[i] = 0;
		}
	}
	answer.pb(cur);


	// (10-19) B: check hundred's digit
	for(int D=0; D<=9; D++){
		cur[0] = 1; // inspect bag B!
		for(int i=2; i<N; i++){
			digit = (i%1000)/100;
			if(digit<D){
				cur[i] = -2;
			} else if(digit>D){
				cur[i] = -1;
			} else{
				cur[i]=7;
			}
		}
		answer.pb(cur);
	}
	
	derr<<"the first index of (20-29) will be "<<answer.size()<<"!\n";
	// (20-29) B: check ten's digit
	for(int D=0; D<=9; D++){
		cur[0] = 1; // inspect bag B!
		for(int i=2; i<N; i++){
			digit = (i%100)/10;
			if(digit<D){
				cur[i] = -2;
			} else if(digit>D){
				cur[i] = -1;
			} else{
				cur[i]=8;
			}
		}
		answer.pb(cur);
	}

	// (30-39) B: check one's digit
	for(int D=0; D<=8; D++){
		cur[0] = 1; // inspect bag B!
		for(int i=2; i<N; i++){
			digit = (i%10);
			if(digit<D){
				cur[i] = -2;
			} else if(digit>D){
				cur[i] = -1;
			} else{
				cur[i]=0; // although this should technically never happen...
			}
		}
		answer.pb(cur);
	}

	derr<<"answer has length "<<answer.size()<<"\n";

	
	

	return answer;
}

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