Submission #767533

#	Time	Username	Problem	Language	Result	Execution time	Memory
767533		Ahmed57	Cave (IOI13_cave)	C++17	0 / 100	63 ms	368 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 i = l;i<=mid;i++){
                if(D[i]==-1){
                    S[i] = 1-S[i];
                }
            }
            int z = tryCombination(S);
            for(int i = l;i<=mid;i++){
                if(D[i]==-1){
                    S[i] = 1-S[i];
                }
            }
            if(z>i){
                l = mid+1;
            }else r = mid;
        }
    }
    answer(S,D);
}
/*
int main(){

}*/

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