제출 #1359565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1359565		OgradL	Prisoner Challenge (IOI22_prison)	C++20	100 / 100	4 ms	1348 KiB

prison

#include "prison.h"

#include <cassert>
#include <functional>
#include <vector>
using namespace std;

vector<vector<int>> devise_strategy(int N){

	const int X = 20;

	vector<vector<int>> ans(X+1, vector<int>(N+1, 0));

	vector<vector<int>> numbers(5104);

	function<void(int, int, int, int)> rec = [&](int reall, int realr, int cnt, int bit) -> void {
		if (cnt <= 0)
			return;

		assert(realr - reall == cnt);

		int pw = bit < 4 ? 3 : 2;

		int nxt = (cnt - 2) / pw;

		numbers[reall].push_back(-10);
		numbers[realr-1].push_back(10);
		for (int x = 1; x < cnt - 1; x++){
			int this_val = (x-1) / nxt;
			numbers[reall + x].push_back(this_val);
		}

		for (int t = 0; t < pw; t++){
			rec(reall + 1 + nxt * t, reall + 1 + nxt * (t+1), nxt, bit+1);
		}
	};

	rec(1, 5103, 5102, 0);


	ans[0][0] = 1;
	for (int i = 1; i <= N; i++){
		int this_val = numbers[i][0];

		if (this_val < 0){
			ans[0][i] = -2;
		} else if (this_val > 4){
			ans[0][i] = -1;
		} else {
			ans[0][i] = 1 + this_val;
		}
	}

	int st = 1;
	for (int bit = 0; bit < 8; bit++){
		int pw = bit < 4 ? 3 : 2;
		int nxt_st = st + pw;
		int turn = bit & 1;

		for (int j = st; j < nxt_st; j++){
			int other_val = j - st;

			ans[j][0] = turn;
			for (int i = 1; i <= N; i++){
				if (numbers[i].size() < bit + 2){
					int last = numbers[i].back();

					if (last < 0){
						ans[j][i] = -1 - turn;
					} else {
						ans[j][i] = -2 + turn;
					}

					continue;
				}
				int this_val = numbers[i][bit];
				int next_val = numbers[i][bit+1];

				if (this_val < other_val){
					ans[j][i] = -1 - turn;
				} else if (this_val > other_val){
					ans[j][i] = -2 + turn;
				} else {
					if (next_val < 0){
						ans[j][i] = -1 - turn;
					} else if (next_val > 4){
						ans[j][i] = -2 + turn;
					} else {
						ans[j][i] = nxt_st + next_val;
					}
				}
			}
		}
		st = nxt_st;
	}

	return ans;
}

• 서브태스크 1: 5 / 5
• 서브태스크 2: 5 / 5
• 서브태스크 3: 90 / 90