| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 171711 | Lukoloz | 동굴 (IOI13_cave) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define MAXN 5005
#define pb push_back
using namespace std;
// int nn,cor[MAXN],cord[MAXN],per[MAXN];
// int tryCombination(bool comb[]){
// bool temp1[nn];
// for (int i=0; i<nn; i++){
// cout<<comb[i]<<" ";
// temp1[per[i]]=comb[i];
// }
// for (int i=0; i<nn; i++){
// if (temp1[i]!=cord[i]) { cout<<" - "<<i<<endl; return i; }
// }
// cout<<" - "<<-1<<endl;
// return -1;
// }
// void answer(bool comb[],int ans[]){
// for (int i=0; i<nn; i++) cout<<comb[i]<<" "; cout<<endl;
// for (int i=0; i<nn; i++) cout<<ans[i]<<" "; cout<<endl;
// }
void exploreCave(int n){
bool fl[n],comb[n],closp;
int ans[n],bl,br,bm;
for (int i=0; i<n; i++) fl[i]=0;
for (int i=0; i<n; i++){
// cout<<" -- "<<i<<" -- "<<endl;
for (int j=0; j<n; j++){
if (fl[j]) continue;
comb[j]=0;
}
// cout<<"comb array - "; for (int j=0; j<n; j++) cout<<comb[j]<<" "; cout<<endl;
if (tryCombination(comb)!=i){
for (int j=0; j<n; j++){
if (fl[j]) continue;
comb[j]=1;
}
closp=1;
} else closp=0;
// cout<<"closp - "<<closp<<endl;
bl=0; br=n-1;
while(bl<br){
bm=(bl+br)/2;
for (int j=bl; j<=bm; j++){
if (fl[j]) continue;
comb[j]=!closp;
}
if (tryCombination(comb)!=i) br=bm;
else bl=bm+1;
for (int j=bl; j<=bm; j++){
if (fl[j]) continue;
comb[j]=closp;
}
}
ans[bl]=i;
comb[bl]=!closp;
// cout<<bl<<endl;
// cout<<comb[bl]<<endl;
fl[bl]=1;
}
answer(comb,ans);
}
int main(){
// cin>>nn;
// for (int i=0; i<nn; i++) cin>>cor[i];
// for (int i=0; i<nn; i++) cin>>per[i];
// for (int i=0; i<nn; i++) cord[per[i]]=cor[i];
// exploreCave(nn);
}
/*
4
1 1 1 0
3 1 0 2
*/