Submission #335264

#	Time	Username	Problem	Language	Result	Execution time	Memory
335264		bigDuck	Cave (IOI13_cave)	C++14	100 / 100	272 ms	748 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll








int n;

int s[5010];
int  d[5010];
bool v[5010];


/*void answer(int S[],int D[]){
cout<<"S: ";
for(int i=0; i<n; i++){
    cout<<s[i]<<" ";
}cout<<"\n";

cout<<"D: ";
for(int i=0; i<n; i++){
    cout<<d[i]<<" ";
}cout<<"\n"<<flush;


}*/



/*int tryCombination(int S[]){

for(int i=0; i<n; i++){
    cout<<s[i]<<" ";
}cout<<"\n"<<flush;
int res;
cin>>res;
return res;
}*/


void door_state(int ind, bool &st){

int crd=tryCombination(s);
crd--;
if( (crd>=ind) || (crd==-2) ){
    st=true;
}
else{
    st=false;
}

return;
}



void query(int ind, bool &st){


int l=0, r=(n-1), m=(l+r)>>1;
//st-state: 0-closed, 1-open;


while(l<r){
        m=(l+r)>>1;
    for(int i=l; i<=m; i++){
        if(!v[i]){
            s[i]=s[i]^1;
        }
    }
    bool st0=st;
    door_state(ind, st);

    if(st0!=st){
        r=m; m=(l+r)>>1; continue;
    }


    l=(m+1); m=(l+r)>>1;

}

if(st==false){
    s[m]^=1;
}
d[m]=ind;
v[m]=true;

}








void exploreCave(int N){
n=N;

for(int i=0; i<n; i++){
    bool st=false;
    door_state(i, st);
    query(i, st);
}

answer(s, d);

}

















/*int32_t main(){
INIT
int N; cin>>N;
exploreCave(N);





return 0;
}*/

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24