# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1177500 | kadir | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#include<bits/stdc++.h>
#define ll int
#define ff first
#define ss second
#define pb push_back
using namespace std;
const ll mod=1e9+7;
const ll inf=1e9;
const ll mxn=2e5+5;
void exploreCave(int n){
int s[n],d[n];
vector<bool> d(n,0);
for(int i=0; i<n; i++) {
vector<int> v;
for(int j=0; j<n; j++) {
if(!d[j]) {
v.pb(j);
}
}
int sz=v.size(),l=0,r=v.size()-1;
for(int j=0; j<v.size(); j++) {
s[v[j]]=0;
}
int x=tryCombination(s);
int q=0,p=1;
if(x==i) {
swap(q,p);
}
while(l<r) {
int mid=(l+r)/2;
for(int j=0; j<sz; j++) {
if(j<=mid) {
s[v[j]]=q;
} else {
s[v[j]]=p;
}
}
x=tryCombination(s);
if(x==-1||x>i) {
r=mid;
} else {
l=mid+1;
}
}
d[v[l]]=i;
s[v[l]]=q;
d[v[l]]=true;
}
answer(s,d);
}