Submission #1264833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264833		avohado	Cave (IOI13_cave)	C++20	100 / 100	125 ms	528 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
void exploreCave(int n){
    int f=0, k; bool b=0;
    int used[n]{}, a[n]{}, kr[n];
    if(tryCombination(a)==f){
        b=1;
    }
    while(f<n){
        int l=0, r=n;
        while(l<r-1){
            int m=(l+r)/2;
            for(int i=l; i<m; i++){
                if(!used[i]){
                    a[i]=(a[i]^1);
                }
            }
            k=tryCombination(a);
            if((k==f)==b){
                l=m;
            }else{
                r=m; b^=1;
            }
        }
        used[l]=1;
        kr[l]=f;
        f++;
        if(b==1){
            a[l]^=1;
            b=(tryCombination(a)==f);
        }else if(f!=n){
            b=(k==f);
        }
    }
    answer(a, kr);
}

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