Submission #767536

#	Time	Username	Problem	Language	Result	Execution time	Memory
767536		Ahmed57	Cave (IOI13_cave)	C++17	100 / 100	227 ms	488 KiB

cave

#include "cave.h"
#include<bits/stdc++.h>

using namespace std;

void exploreCave(int N){
    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rng(1, (1ll<<20));
    int S[N] , D[N];
    for(int i = 0;i<N;i++){
        S[i] = 0;
        D[i] = -1;
    }
    for(int i = 0;i<N;i++){
        int x = tryCombination(S);
        int l = 0 , r = N-1;
        while(1){
            if(l==r){
                if(x==i){
                    S[l] = 1-S[l];
                }
                D[l] = i;
                break;
            }
            int mid = (l+r)/2;
            for(int j = l;j<=mid;j++){
                if(D[j]==-1){
                    S[j] = 1-S[j];
                }
            }
            int z = tryCombination(S);
            for(int j = l;j<=mid;j++){
                if(D[j]==-1){
                    S[j] = 1-S[j];
                }
            }
            if((z==i&&i!=x)||(z!=i&&i==x)){
                r = mid;
            }else l = mid+1;
        }
    }
    answer(S,D);
}
/*
int main(){

}*/

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