| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1043179 | Marco_Escandon | 죄수들의 도전 (IOI22_prison) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
//#include "prison.h"
typedef int ll;
vector<vector<ll>> s;
ll cad[]={ 3, 3, 3, 3, 3, 2, 2, 1};
//ll cad[]={ 1,2,2,3,3,3,3,3};
ll P[22][5588]={ };
void sol(ll p,ll a, ll b)
{
if(a>=b) return;
P[p][a]=-1e9;
P[p][b]=1e9;
if(a+1==b) return;
ll t1=(b-a-1)/cad[p];
ll t2=(b-a-1)%cad[p];
ll c=0;
for(int i=a+1; i<b;c++)
{
for(int j=0;j<t1+t2; j++)
{
P[p][i+j]=c;
}
sol(p+1,i,i+t1+t2-1);
i=i+t1+t2;
t2--;t2=max(t2,0);
}
}
ll Hash(ll p, ll vp) { return vp*9+p; }
std::vector<std::vector<int>> devise_strategy(int n) {
sol(0,1,5588);
s.assign(22,vector<ll>(n+1,0));
s[0][0]=0;s[0][1]=-1;s[0][n]=-2;
for(int i=2; i<n; i++)
s[0][i]=Hash(0,P[0][i])+1;
for(int i=1; i<21; i++)
{
s[i][0]=max((i%2),0);
ll temp=i-1;
ll va=temp%9;
temp/=9;
swap(va,temp);
for(int j=1; j<=n; j++)
{
ll vp=P[temp][j];
if(va==vp)s[i][j]=Hash(temp+2,P[temp+1][j]);
else if((s[i][0]==0&&vp<va)||(s[i][0]==1&&vp>va)) s[i][j]=-1;
else s[i][j]=-2;
if(s[i][j]>=22) s[i][j]=-2+s[i][0];
if(s[i][j]<-1e7) s[i][j]=-1-s[i][0];
}
}
return s;
}
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
static constexpr int kNumPrisoners = 500;
static void invalid_strategy(std::string message) {
printf("%s\n", message.c_str());
exit(0);
}
int main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<std::vector<int>> strategy = devise_strategy(N);
if (strategy.size() == 0) {
invalid_strategy("s is an empty array");
}
int x = strategy.size() - 1;
for (int i = 0; i <= x; ++i) {
if (static_cast<int>(strategy[i].size()) != N + 1) {
invalid_strategy("s[i] contains incorrect length");
}
if (strategy[i][0] < 0 || strategy[i][0] > 1) {
invalid_strategy("First element of s[i] is non-binary");
}
for (int j = 1; j <= N; ++j) {
if (strategy[i][j] < -2 || strategy[i][j] > x) {
invalid_strategy("s[i][j] contains incorrect value");
}
}
}
int A, B;
while (1 == scanf("%d", &A) && A != -1) {
assert(1 == scanf("%d", &B));
bool answer = false;
int whiteboard = 0;
for (int i = 0; i < kNumPrisoners && !answer; ++i) {
int check = strategy[whiteboard][0];
whiteboard = strategy[whiteboard][check == 0 ? A : B];
if (whiteboard < 0) {
answer = true;
printf("%c\n", "BA"[whiteboard + 2]);
} else {
if (i > 0) {
printf(" ");
}
printf("%d", whiteboard);
}
}
if (!answer) {
printf("X\n");
}
printf("\n");
}
}