Submission #1125567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125567		Francisco_Martin	Cave (IOI13_cave)	C++20	100 / 100	299 ms	532 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define ll int

void exploreCave(ll n){
    ll S[n], D[n], ans, l, r, ract, res;
    for(int i=0; i<n; i++) S[i]=D[i]=-1;
    for(int i=0; i<n; i++){
        ll act[n];
        for(int j=0; j<n; j++){
            if(S[j]!=-1) act[j]=S[j];
            else act[j]=0;
        }
        ans=tryCombination(act);
        if(ans==-1 || ans>i) ract=0;
        else ract=1;
        l=0; r=n-1; res=n;
        while(l<=r){
            ll m=(l+r)/2;
            for(int j=0; j<m; j++){
                if(S[j]!=-1) act[j]=S[j];
                else act[j]=ract^1;
            }
            for(int j=m; j<n; j++){
                if(S[j]!=-1) act[j]=S[j];
                else act[j]=ract;
            }
            ans=tryCombination(act);
            if(ans==-1 || ans>i){
                l=m+1;
                res=m;
            }else r=m-1;
        }
        D[res]=i;
        S[res]=ract;
    }
    answer(S,D);
}

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