| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1038508 | attky | 동굴 (IOI13_cave) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int n) {
int state[n], pos[n];
bool good[n];
for(int loop = 0; loop < n; ++loop) {
good[loop] = false;
pos[loop] = -1;
}
for(int loop = 0; loop < n; ++loop) {
for(int looping = 0; looping < n; ++looping) {
if(!good[looping]) {
state[looping] = 1;
}
}
int ans = tryCombination(state)-1;
if(ans < 0) {
ans = 2e9;
}
bool closed = (ans == loop);
int deb = 0, fin = n-1;
while(fin-deb > 0) {
int mid = (deb+fin)/2;
for(int looping = mid+1; looping <= fin; ++looping) {
if(!good[looping]) {
state[looping] = 1-state[looping];
}
}
int newAns = tryCombination(state)-1;
if(newAns < 0) {
newAns = 2e9;
}
bool newClosed = (ans == loop);
if((newClosed && closed) || (!newClosed && !closed)) {
fin = mid;
}
else {
deb = mid+1;
}
}
good[deb] = true;
pos[deb] = loop+1;
}
answer(state, pos);
}