Submission #377119

#	Time	Username	Problem	Language	Result	Execution time	Memory
377119		kevinxiehk	Cave (IOI13_cave)	C++17	25 / 100	806 ms	704 KiB

cave

#include"cave.h"
#ifdef __cplusplus
extern "C" {
#endif
int tryCombination(int S[]);
void answer(int S[], int D[]);
void exploreCave(int N);
#ifdef __cplusplus
}
#endif

// TODO: global variables can be declared here
void exploreCave(int N){
    int test[N],open[N],corr[N],cor[N];
    for(int i=0;i<N;i++){
        int l=0,r=N-1;
        for(int j=l;j<=r;j++)test[j]=0;
        for(int j=0;j<i;j++)test[corr[j]]=open[j];
        int a=tryCombination(test);
        if(a==-1)a=N+1;
        if(a<=i){
            open[i]=1;
            for(int j=l;j<=r;j++)test[j]=1;
            for(int j=0;j<i;j++)test[corr[j]]=open[j];
        }
        else open[i]=0;
        while(l<r){
            int mid=(l+r)/2+1;
            for(int j=mid;j<=r;j++)test[j]^=1;
            for(int j=0;j<i;j++)test[corr[j]]=open[j];
            a=tryCombination(test);
            if(a==-1)a=N+1;
            if(a<=i){
                for(int j=l;j<=r;j++)test[j]^=1;
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        corr[i]=l;
    }
    for(int i=0;i<N;i++)cor[corr[i]]=i;
    answer(open,cor);
  // TODO: implementation
}

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