제출 #1044850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044850		Dan4Life	죄수들의 도전 (IOI22_prison)	C++17	65 / 100	7 ms	1116 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
const int mxN = (int)1e5+10;
const ll LINF = (ll)2e18;
const int B = 3;
int Pow[B+1][100];

vector<vi> devise_strategy(int N) {
	
	for(int j = 1; j <= B; j++){
		Pow[j][0] = 1;
		for(int i = 1; i < 20; i++) 
			Pow[j][i]=Pow[j][i-1]*j;
	}
	int tot = 1, mxX = 1;
	while(tot*B<=5000) tot*=B, mxX++;
	int lim = mxX-1; mxX*=B;
	vector<vi> ans(mxX+1,vi(N+1,0));
	int fi = 1, cur = 0;
	ans[0][0] = 0; // if we are at 0, inspect A.
	for(int i = 1; i <= N; i++) 
		ans[0][i] = 1+i/Pow[B][lim];
		
	for(int i = lim; i>=0; i--){
		cur^=1;
		for(int j = fi; j < fi+B; j++){
			ans[j][0] = cur;
			for(int k = 1; k <= N; k++){
				int curA=(k%Pow[B][i+1])/Pow[B][i], curB = j-fi;
				if(cur) swap(curA,curB);
				if(curA<curB) ans[j][k]=-1;
				else if(curA>curB) ans[j][k]=-2;
				else if(i) ans[j][k] = fi+B+(k%Pow[B][i])/Pow[B][i-1];
			}
		}
		fi+=B;
	}
	return ans;
}

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