Submission #1137952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137952		mariam197	Cave (IOI13_cave)	C++20	100 / 100	197 ms	516 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
//#include "grader.c"
using namespace std;
int s[5003],k[5003];
void make(int l,int r,int x){
    for(int i=l;i<=r;i++){
        if(k[i]==-1)
            s[i]=x;
    }
}
void exploreCave(int N) {
    memset(k,-1,sizeof k);
    for(int i=0;i<N;i++){
        int x=tryCombination(s);
        int l=0,r=N-1;
        while(l<r){
            int mid=(l+r)/2;
            make(l,mid,1);
            int y=tryCombination(s);
            make(l,mid,0);
            if(x<=i && x!=-1){
                if(y>i || y==-1) r=mid;
                else l=mid+1;
            }
            else{
                if(y<=i && y!=-1) r=mid;
                else l=mid+1;
            }
        }
        if(x<=i && x!=-1) s[l]=1;
        k[l]=i;
    }
    answer(s,k);
}

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