Submission #632202

#	Time	Username	Problem	Language	Result	Execution time	Memory
632202		minhcool	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	11 ms	1368 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, 22, 66, 198, 594, 1782, 5346};
 
vector<vector<int>> devise_strategy(int N){
	n = N;
	if(n <= 20){
		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 <= 4; 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 cell[(i - 1) * 3 + j + 1][k] = i * 3 + 1 + (k % (arr[8 - i])) / arr[7 - i];
				}
			}
		}
		for(int i = 13; i <= 15; i++){
		    int j = (i - 1) % 3;
		    cell[i][0] = 1;
		    for(int k = 1; k <= n; k++){
		        int temp = (k % 66) / 22;
		        if(temp > j) cell[i][k] = -1;
		        else if(temp < j) cell[i][k] = -2;
		        else{
		            if(!(k % 22)) cell[i][k] = -2;
		            else if((k % 22) == 21) cell[i][k] = -1;
		            else{
		                if((k % 22) <= 10) cell[i][k] = 16;
		                else cell[i][k] = 17;
		            }
		        }
		    }
		}
		cell[16][0] = 0;
		for(int k = 1; k <= n; k++){
		    int temp = (k % 22);
		    if(temp <= 1) cell[16][k] = -1;
		    else if(temp >= 10) cell[16][k] = -2;
		    else{
		        if(temp <= 5) cell[16][k] = 18;
		        else cell[16][k] = 19;
		    }
		}
		cell[17][0] = 0;
		for(int k = 1; k <= n; k++){
		    int temp = (k % 22);
		    if(temp <= 11) cell[17][k] = -1;
		    else if(temp >= 20) cell[17][k] = -2;
		    else{
		        if(temp <= 15) cell[17][k] = 18;
		        else cell[17][k] = 19;
		    }
		}
		cell[18][0] = 1;
		for(int k = 1; k <= n; k++){
		    int temp = (k % 22);
		    if(temp <= 10){
		        if(temp >= 5) cell[18][k] = -1;
		        else if(temp <= 2) cell[18][k] = -2;
		        else cell[18][k] = 20;
		    }
		    else{
		        if(temp >= 15) cell[18][k] = -1;
		        else if(temp <= 12) cell[18][k] = -2;
		        else cell[18][k] = 20;
		    }
		}
		cell[19][0] = 1;
		for(int k = 1; k <= n; k++){
		    int temp = (k % 22);
		    if(temp <= 10){
		        if(temp <= 6) cell[19][k] = -2;
		        else if(temp >= 9) cell[19][k] = -1;
		        else cell[19][k] = 20;
		    }
		    else{
		        if(temp <= 16) cell[19][k] = -2;
		        else if(temp >= 19) cell[19][k] = -1;
		        else cell[19][k] = 20;
		    }
		}
		cell[20][0] = 0;
		for(int k = 1; k <= n; k++){
		    int temp = (k % 22);
		    if(temp == 4 || temp == 8) cell[20][k] = -2;
		    else if(temp == 5 || temp == 9) cell[20][k] = -2;
		    else if(temp == 14 || temp == 15) cell[20][k] = -2;
		    else if(temp == 18 || temp == 19) cell[20][k] = -2;
		    else cell[20][k] = -1;
		}
		/*
		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(21);
		for(int i = 0; i <= 20; 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";
				//if(i == 13 && j == 12) cout << i << " " << j << " " << ini << " " << x << " " << (x % 22) << "\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: 90 / 90