Submission #166867

#	Time	Username	Problem	Language	Result	Execution time	Memory
166867		Alabana	Cave (IOI13_cave)	C++11	100 / 100	433 ms	536 KiB

cave

#include "cave.h"
#include <cstdio>
void exploreCave(int N) {
    int S[N],D[N];
    for(int i=0;i<N;i++){
      S[i]=0;
      D[i]=-1;
    }
    for(int i=0;i<N;i++){
      int ini=0, fim=N-1,atual=-1;
      int meio=(ini+fim)/2;
      int a=tryCombination(S);
      if(a>i or a==-1){
        atual=0;
      }
      else{
        atual=1;
      }
      while(ini<fim){
        //printf("%d \n %d %d \n", i, ini, fim);
        meio=(ini+fim)/2;
        for(int j=ini;j<=meio;j++){
          if(D[j]==-1)S[j]=1;
        }
        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;
    }
    answer(S,D);
}

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