제출 #758687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758687		amunduzbaev	죄수들의 도전 (IOI22_prison)	C++17	80 / 100	10 ms	980 KiB

prison

#include "prison.h"

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

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

#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll

vector<vector<ii>> devise_strategy(ii n) {
	vector<vector<ii>> a(1, vector<ii>(n + 1));
	auto get = [&](int x, int b){
		while(b){
			x /= 3;
			b--;
		}
		return x % 3;
	};
	
	a[0][0] = 1;
	for(int i=1;i<=n;i++){
		a[0][i] = a.size() + get(i, 7);
	}
	vector<int> b_(n + 1, 0);
	a.push_back(b_);
	a.push_back(b_);
	a.push_back(b_);
	
	for(int b=6;b>0;b--){
		
		for(int j=(int)a.size() - 3;j<(int)a.size();j++){
			int prev = (j - 1) % 3;
			a[j][0] = b&1;
			for(int i=1;i<=n;i++){
				int cur = get(i, b + 1);
				if(cur < prev){
					if(b&1) a[j][i] = -2;
					else a[j][i] = -1;
				}
				
				if(prev < cur){
					if(b&1) a[j][i] = -1;
					else a[j][i] = -2;
				}
				
				if(prev == cur){
					a[j][i] = a.size() + get(i, b);
				}
			}
		}
		
		a.push_back(b_);
		a.push_back(b_);
		a.push_back(b_);
	}
	
	for(int j=(int)a.size() - 3;j<(int)a.size();j++){
		int prev = (j - 1) % 3;
		a[j][0] = 0;
		for(int i=1;i<=n;i++){
			int cur = get(i, 1);
			if(cur < prev){
				a[j][i] = -1;
			} 
			if(prev < cur){
				a[j][i] = -2;
			} 
			if(prev == cur){
				int nxt = get(i, 0);
				if(nxt == 0){
					a[j][i] = -1;
				} if(nxt == 2){
					a[j][i] = -2;
				} if(nxt == 1){
					a[j][i] = a.size();
				}
			}
		}
	}
	
	a.push_back(b_);
	a.back()[0] = 1;
	for(int i=1;i<=n;i++){
		int cur = get(i, 0);
		if(cur == 0){
			a.back()[i] = -2;
		} if(cur == 2){
			a.back()[i] = -1;
		}
		
	}
	
	return a;
}

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