# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1272710 | zagaro | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "cave.h"
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
void exploreCave(int n) {
int l, r, ind, m, opc, a, b;
vector<int> D(n, -1);
vector<int> S(n);
vector<int> s;
vector<pair<int,int> > vec;
for(int i=0;i<n;i++){
l = 0;
r = n-1;
s.assign(n, 0);
for(int k=0;k<vec.size();k++)s[vec[k].first] = vec[k].second;
opc = tryCombination(s);
if(opc == -1)opc = n+1;
if(opc > i){
a=0;b=1;
S[i] = 0;
for(int k=0;k<n;k++){
if(D[k] == -1)s[k] = b;
}
}
else {a=1;b=0;S[i]=1;}
wl(l < r){
m = (l+r)/2;
for(int k=l;k<=m;k++)if(D[k] == -1)s[k]=a;
opc = tryCombination(s);
if(opc == -1)opc= n+1;
if(opc > i){
for(int k=l;k<=m;k++)if(D[k] == -1)s[k]=b;
r=m;
}
else l = m+1;
}
D[l] = i;
vec.push_back({l,a});
}
answer(S, D);
return ;
}