| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1310761 | jinjikhadzegiorgi | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
void exploreCave(int n) {
// create s, sFinal, dFinal and found arrays
int s[n], sFinal[n], dFinal[n];
bool found[n];
// assign starting value to s and found, 0 to both
for(int i=0; i<n; i++){
s[i]=0;
found[i]=false;
}
// start finding which swich opens door i
for(int i=0; i<n; i++){
// reset the ones that we didnt explore
for(int j=0; j<n; j++){
if(!found[j])s[j]=0;
}
// check if ith door will open
int res=tryCombination(s);
int targetState;
if(res==-1 || res>i){
// if yes, set val to 0
targetState=0;
}else{
// if nah, set val to 1
targetState=1;
}
// left, right, and switch for ith door
int l=0; int r=n-1; int scwch=-1;
while(l<=r){
// find middle
int m=(l+r)/2;
// set all unexplored switches in left half
for(int j=i; j<n; j++){
if(!found[j]){
if(j>=l && j<=m){
s[j]=targetState;
}else{
s[j]=1-targetState;
}
}
}
// check in which half our switch is located at
int res2=tryCombination(s);
if(res2==-1 || res2>i){
r=m-1;
swch=m;
}else{
l=m+1;
}
}
// update found, sFinal, dFinal and s arrays
found[swch]=true;
sFinal[swch]=targetState;
dFinal[swch]=i;
s[swch]=targetState;
}
// print answer
answer(sFinal, dFinal);
}