Submission #627346

#	Time	Username	Problem	Language	Result	Execution time	Memory
627346		minhcool	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	13 ms	1492 KiB

prison

#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 5005;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n;

int cell[N][N];

int arr[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};

vector<vector<int>> devise_strategy(int N){
	n = N;
	if(n <= 22){
		cell[0][0] = 0;
		for(int i = 1; i <= n; i++) cell[0][i] = i;
		for(int i = 1; i <= n; i++){
			cell[i][0] = 1;
			for(int j = 1; j <= n; j++){
				cell[i][j] = (i < j ? -1 : -2);
			}
		}
		vector<vector<int>> ans;
		ans.resize(n + 1);
		for(int i = 0; i <= n; i++){
			ans[i].resize(n + 1);
			for(int j = 0; j <= n; j++) ans[i][j] = cell[i][j];
		}
		return ans;
	}
	else{
		cell[0][0] = 0;
		for(int i = 1; i <= n; i++) cell[0][i] = 1 + (i % arr[8]) / arr[7];
		for(int i = 1; i <= 7; i++){
			for(int j = 0; j < 3; j++){
				cell[(i - 1) * 3 + j + 1][0] = (i & 1);
				for(int k = 1; k <= n; k++){
					int temp = (k % arr[9 - i]) / arr[8 - i];
					if(temp > j) cell[(i - 1) * 3 + j + 1][k] = ((i & 1) ? -1 : -2);
					else if(temp < j) cell[(i - 1) * 3 + j + 1][k] = ((i & 1) ? -2 : -1);
					else if(i <= 6){
						cell[(i - 1) * 3 + j + 1][k] = i * 3 + 1 + (k % (arr[8 - i])) / arr[7 - i];
					}
					else if(i == 7 && (k % 3) == 2) cell[(i - 1) * 3 + j + 1][k] = ((i & 1) ? -1 : -2);
					else if(i == 7 && (k % 3) == 0) cell[(i - 1) * 3 + j + 1][k] = ((i & 1) ? -2 : -1);
					else cell[(i - 1) * 3 + j + 1][k] = 22;
				}
			}
		}
		cell[22][0] = 0;
		for(int i = 1; i <= n; i++){
			if(i % 3 == 0) cell[22][i] = -1;
			else cell[22][i] = -2;
		}
		vector<vector<int>> ans;
		ans.resize(23);
		for(int i = 0; i <= 22; i++){
			ans[i].resize(n + 1);
			for(int j = 0; j <= n; j++) ans[i][j] = cell[i][j];
		}
		return ans;
	}
}

/*
void process(){
	int n;
	cin >> n;
	vector<vector<int>> a = devise_strategy(n);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			int ini = 0;
			for(int turn = 1; turn <= 500; turn++){
				if(turn > 500){
					cout << i << " " << j << "\n";
					return;
				}
				int x = (cell[ini][0] == 0 ? i : j);
				//if(i == 1 && j == 2187) cout << ini << " " << x << "\n";
				ini = cell[ini][x];
				if(ini < 0){
					//cout << ini << "\n";
					if(ini == -1 && (i < j)) break;
					if(ini == -2 && (i > j)) break;
					cout << i << " " << j << "\n";
					return;
				}
			}
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}
*/

Compilation message (stderr)

prison.cpp:18:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

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