Submission #1287993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287993		eri16	Cave (IOI13_cave)	C++20	100 / 100	121 ms	524 KiB

cave

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



void exploreCave(int n){
    
    int d[n],v[n],fnd[n];
    
    for (int i=0; i<n; i++){
        v[i]=0;
        fnd[i]=0;
    }

    int ans,cr1,cr2;
    
    queue <int> q;
    
    int tt=0;
    int fns=0;
    
    cr1=tryCombination(v);
    
    for (int j=0; j<n; j++){
    
        int l=0;
        int r=n-1;
        while(l!=r){
        int md=(l+r)/2;
        for(int i=l; i<=md; i++){if(fnd[i]==0){v[i]=1-v[i];}}        
        
        cr2=tryCombination(v);
        
        if ((cr2==j && cr1!=j) || (cr2!=j && cr1==j)){r=md;}
        else{l=min(r,md+1);}
        cr1=cr2;
        }
        if (cr1==j){v[l]=1-v[l];cr1=tryCombination(v);}
        
        fnd[l]=1;
        d[l]=j;
        
    }

    answer(v,d);
}

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