제출 #1058289

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

prison

#include <bits/stdc++.h>
#include "prison.h"

using namespace std;

const int Lg = 8;

char int_to_char(int x)
{
	if(x == 0)
		return '0';
	else if(x == 1)
		return '1';
	else
		return '2';
}

int char_to_int(char c)
{
	if(c == '0')
		return 0;
	else if(c == '1')
		return 1;
	else		
		return 2;
}

string int_to_ter(int x)
{
	string s = "";
	for(int i = 0 ; i < Lg ; i++)
	{
		s.push_back(int_to_char(x % 3));
		x /= 3;
	}
	return s;
}

int f(int x)
{
	if(x >= 3)
		return x - 1;
	return x;
}

int revf(int x)
{
	if(x >= 2)
		return x + 1;
	return x;
}

vector<vector<int>>  devise_strategy(int n)
{
	vector <vector<int>> res;
	for(int i = 0 ; i <= 22 ; i++)
	{
		vector <int> vec(n + 1 , 0);
		res.push_back(vec);
	}
	for(int i = 0 ; i <= 22 ; i++)
	{
		if(i == 0)
		{
			res[i][0] = 1;
			for(int j = 1 ; j <= n ; j++)
			{
				string s = int_to_ter(j);
				res[i][j] = f(3 * 7 + char_to_int(s[7]));
			}
			continue;
		}
		int bit = revf(i) / 3 , val = revf(i) % 3;
		if(bit % 2 == 0)
			res[i][0] = 1;
		else
			res[i][0] = 0;
		for(int j = 1 ; j <= n ; j++)
		{
			string s = int_to_ter(j);
			int v = char_to_int(s[bit]);
			if(v != val)
			{
				if(val > v)
				{
					if(res[i][0] == 0)
						res[i][j] = -1;
					else
						res[i][j] = -2;
				}
				else
				{
					if(res[i][0] == 0)
						res[i][j] = -2;
					else
						res[i][j] = -1;
				}
			}
			else
			{
				if(bit == 0)
					continue;
				v = char_to_int(s[bit - 1]);
				if(bit == 1 && v == 0)
				{
					res[i][j] = -1;
					continue;
				}
				if(bit == 1 && v == 2)
				{
					res[i][j] = -2;
					continue;
				}
				res[i][j] = f(3 * (bit - 1) + v);
			}
		}
	}
	return res;
}

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