| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 852873 | Bach21 | 동굴 (IOI13_cave) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int nmax=5e3+5;
int qarr[nmax],check[nmax],res[nmax],res1[nmax];
int N;
bool checker(int tmp,int tar)
{
if (tmp==-1) return 1;
return (tmp>tar);
}
void solve(int tar,int l,int r,int known)
{
if (l==r)
{
res[l]=known;
check[l]=1;
res1[l]=tar;
}
memset(qarr,0,sizeof qarr);
int mid=(l+r) >> 1;
for (int i=0;i<N;i++)
{
if (i>=l && i<=mid)
{
qarr[i]=known;
} else
qarr[i]=1^known;
}
for (int i=0;i<N;i++)
{
if (check[i]) qarr[i]=res[i];
}
int ans=tryCombination(qarr);
if (checker(ans,tar))
{
solve(tar,l,mid,known);
} else solve(tar,mid+1,r,known);
}
int findcolor(int tar)
{
memset(qarr,0,sizeof qarr);
for (int i=0;i<N;i++)
{
if (check[i]) qarr[i]=res[i];
}
int ans=tryCombination(qarr);
if (checker(ans,tar)) return 0; else return 1;
}
void explorecave(int n)
{
int N=n;
for (int i=0;i<N;i++)
{
int color= findcolor(i);
solve(i,0,N-1,color);
}
answer(res,res1);
}