Submission #1169779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169779		thelegendary08	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	1096 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(x) for(auto u : x)cout<<u<<' ';cout<<'\n';
using namespace std;
vi tern(int x){
	int cur = 1;
	vi ret;
	while(x > 0){
		ret.pb(x % (cur * 3) / cur);
		x -= (x % (cur * 3));
		cur *= 3;
	}
	while(ret.size() < 8)ret.pb(0);
	reverse(ret.begin(), ret.end());
	return ret;
}
std::vector<std::vector<int>> devise_strategy(int N) {
	vector<vi>v(23, vi(N+1));
	v[0][0] = 0;
	FOR(i, 1, N+1){
		vi cur = tern(i);
		v[0][i] = 1 + cur[0];
	}
	FOR(dig, 1, 8){
		if(dig % 2 == 1){
			v[dig * 3 - 2][0] = 1;
			v[dig * 3 - 1][0] = 1;
			v[dig * 3][0] = 1;
		}
		else{
			v[dig * 3 - 2][0] = 0;
			v[dig * 3 - 1][0] = 0;
			v[dig * 3][0] = 0;
		}
		//v[2][1] is -2
		//v[1][2] is -1
		FOR(i, 1, N+1){
			vi cur = tern(i);
			f0r(j, 3){
				if(dig != 8){
					if(cur[dig-1] < j){
						v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -2 : -1);
					}
					else if(cur[dig-1] > j){
						v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -1 : -2);
					}
					else{
						if(dig != 7)v[(dig - 1) * 3 + 1 + j][i] = dig * 3 + 1 + cur[dig];
						else{
							if(cur[dig] == 0){
								v[(dig - 1) * 3 + 1 + j][i] = -2;
							}
							else if(cur[dig] == 2){
								v[(dig - 1) * 3 + 1 + j][i] = -1;
							}
							else{
								v[(dig - 1) * 3 + 1 + j][i] = 22;
							}
						}
					}
				}
				else{
					if(cur[dig-1] < j){
						v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -2 : -1);
					}
					else if(cur[dig-1] > j){
						v[(dig - 1) * 3 + 1 + j][i] = (dig % 2 == 1 ? -1 : -2);
					}
				}
				
			}
		}
	}
	v[22][0] = 0;
	
	FOR(i, 1, N+1){
		vi cur = tern(i);
		if(cur[7] == 0){
			v[22][i] = -1;
		}
		else v[22][i] = -2;
	}
	
	/*
	f0r(i, 23){
		f0r(j, 11)cout<<v[i][j]<<' ';
		cout<<'\n';
	}
	*/
	return v;
	
}

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