| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1310674 | putuputu | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n) #include "cave.h"
#include<bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
vector<int> s(n, 0);
vector<int> use(n, 0);
vector<int> dswitch(n, -1);
vector<int> state(n, 0);
for(int i=0; i<n; i++){
vector<int>c;
for(int j=0; j<n; j++){
if(!use[j]){
c.push_back(j);
}
}
int l=0, r=(int)c.size()-1;
int find=-1;
while(l<=r){
int m=(l+r)/2;
for(int j=0; j<n; j++){
s[j]=0;
}
for(int j=0; j<i; j++){
s[dswitch[j]]=state[j];
}
for(int j=l; j<=m; j++){
s[c[j]]=1;
}
int res=tryCombination(s.data());
if(res==-1 or res>i){
find=c[m];
r=m-1;
}else{
l=m+1;
}
}
for(int j=0; j<n; j++){
s[j]=0;
}
for(int j=0; j<i; j++){
s[dswitch[j]]=state[j];
}
s[find]=0;
int res=tryCombination(s.data());
int need;
if(res==-1 or res>i){
need=0;
}else{
need=1;
}
use[find]=1;
dswitch[i]=find;
state[i]=need;
}
answer(dswitch.data(), state.data());
}
