Submission #630217

#	Time	Username	Problem	Language	Result	Execution time	Memory
630217		amunduzbaev	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	16 ms	1364 KiB

prison

#include "prison.h"
#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

const int p = 3;

vector<vector<int>> devise_strategy(int n) {
	int b = 7, last = 0;
	vector<vector<int>> res;
	vector<int> v(n + 1);
	
	vector<vector<int>> bit(n + 1, vector<int>(b + 1));
	for(int i=1;i<=n;i++){
		int x = i;
		for(int j=0;j<=b;j++){
			bit[i][j] = x % p;
			x /= p;
		}
	}
	
	int is = 0, nxt = 4, cur = 0;
	while(~b){
		res.push_back(v);
		if(!last){
			last++;
			res[last - 1][0] = 0;
			for(int j=1;j<=n;j++){
				res[last - 1][j] = last + bit[j][b];
			}
		} else {
			if(!b){
				if(is){
					for(int j=1;j<=n;j++){
						if(bit[j][b] == 1) continue;
						if(bit[j][b] == 0) res[last][j] = -1;
						else res[last][j] = -2;
					}
				} else {
					res[last][0] = 1;
					for(int j=1;j<=n;j++){
						if(bit[j][b] == 1) continue;
						if(bit[j][b] == 0) res[last][j] = -2;
						else res[last][j] = -1;
					}
				}
				break;
			}
			if(is){
				res[last][0] = 0;
				for(int j=1;j<=n;j++){
					if(bit[j][b] == cur){
						if(b == 1){
							if(bit[j][b - 1] == 0) res[last][j] = -1;
							if(bit[j][b - 1] == 2) res[last][j] = -2;
							if(bit[j][b - 1] == 1) res[last][j] = nxt;
						} else if(b > 0) res[last][j] = nxt + bit[j][b - 1];
					} else {
						if(bit[j][b] > cur){
							res[last][j] = -2;
						} else {
							res[last][j] = -1;
						}
					}
				}
				
				if(last % 3 == 0){
					b--;
					is ^= 1;
					nxt += 3;
				}
				
				cur = (cur + 1) % 3;
				last++;
			} else {
				res[last][0] = 1;
				for(int j=1;j<=n;j++){
					if(bit[j][b] == cur){
						if(b == 1){
							if(bit[j][b - 1] == 0) res[last][j] = -2;
							if(bit[j][b - 1] == 2) res[last][j] = -1;
							if(bit[j][b - 1] == 1) res[last][j] = nxt;
						} else if(b > 0) res[last][j] = nxt + bit[j][b - 1];
					} else {
						if(bit[j][b] > cur){
							res[last][j] = -1;
						} else {
							res[last][j] = -2;
						}
					}
				}
				if(last % 3 == 0){
					b--;
					is ^= 1;
					nxt += 3;
				}
				
				cur = (cur + 1) % 3;
				last++;
			}
			
			
		}
	}
	
	//~ for(auto v : res){
		//~ for(auto x : v) cout<<x<<" ";
		//~ cout<<endl;
	//~ } cout<<endl;
	
	//~ for(int j=0;j<last;j++){
		//~ for(int i=0;i<=n;i++) cout<<res[j][i]<<" ";
	//~ } cout<<"\n";
	
	return res;
}

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