| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 839277 | Alfraganus | 동굴 (IOI13_cave) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cave.h"
#include "grader.c"
#include <vector>
using namespace std;
bool used[5001];
int bits[5001], a[5001];
bool check(int l, int r){
for(int i = l; i <= r; i ++)
if(!used[i])
return false;
return true;
}
void color(int l, int r, int x){
for(int i = l; i <= r; i ++)
if(!used[i])
bits[i] = x;
}
void exploreCave(int n){
for(int i = 0; i < n; i ++){
int l = 0, r = n - 1;
int x = -1;
while(l < r){
int m = (l + r) >> 1;
if(check(l, m))
l = m + 1;
else if(check(m + 1, r))
r = m;
else{
color(l, m, 0);
color(m + 1, r, 1);
int k = tryCombination(bits);
if(x == -1){
if(k > i or k == -1){
color(m + 1, r, 0);
int k = tryCombination(bits);
if(k > i or k == -1)
x = 0, r = m;
else
x = 1, l = m + 1;
}
else{
color(m + 1, r, 0);
int k = tryCombination(bits);
if (k > i or k == -1)
x = 0, l = m + 1;
else
x = 1, r = m;
}
}
else{
if(k > i or k == -1)
l = m + 1;
else
r = m;
}
}
}
if(i == n - 1){
color(0, n - 1, 0);
x = 0;
if(tryCombination(bits) != -1)
x = 1;
}
used[l] = true;
bits[l] = x;
a[l] = i;
}
answer(bits, a);
}