Submission #166743

#	Time	Username	Problem	Language	Result	Execution time	Memory
166743		Alabana	Cave (IOI13_cave)	C++14	51 / 100	376 ms	512 KiB

cave

#include "cave.h"

void exploreCave(int N) {
    int S[N],D[N];
		for(int i=0;i<N;i++){
			S[i]=0;
			D[i]=-1;
		}
		int i=0;
		while(i<N){
			int ini=0, fim=N-1,atual=-1;
      int meio=(ini+fim)/2;
			if(tryCombination(S)>i or tryCombination(S)==-1){
				atual=0;
			}
			else{
				atual=1;
			}
      while(ini<fim){

        meio=(ini+fim)/2;
        for(int j=ini;j<=meio;j++){
          if(D[j]==-1)S[j]=1;
        }
        int a=tryCombination(S);
        if((atual==1 and (a>i or a==-1)) or (atual==0 and a==i)){
          for(int j=ini;j<=meio;j++){
            if(D[j]==-1)S[j]=0;
          }
          fim=meio;
        }
        else if((atual==1 and a==i) or (atual==0 and (a>i or a==-1))){
          if(ini==fim-1){
            D[fim]=i;
          }
          for(int j=ini;j<=meio;j++){
            if(D[j]==-1)S[j]=0;
          }
          ini=meio+1;
        }
      }
      S[ini]=atual;
      D[ini]=i;
      i++;
		}
    answer(S,D);
}

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