Submission #258727

#	Time	Username	Problem	Language	Result	Execution time	Memory
258727		davi_bart	Cave (IOI13_cave)	C++14	100 / 100	1043 ms	632 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define ll long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int tryCombination(int S[]);
void answer(int S[], int D[]);
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++){
    for(int j=0;j<N;j++){
      if(D[j]!=-1)continue;
      S[j]=1;
    }
    int x=tryCombination(S);
    if(x==-1 || x>i){
      int l=0,r=N-1;
      while(l<r){
        int m=(l+r)/2;
        for(int h=0;h<N;h++){
          if(D[h]!=-1)continue;
          if(h<=m)S[h]=1;
          else S[h]=0;
        }
        int x=tryCombination(S);
        if(x==-1 || x>i)r=m;
        else l=m+1;
      }
      D[r]=i;
      S[r]=1;
    }else{
      int l=0,r=N-1;
      while(l<r){
        int m=(l+r)/2;
        for(int h=0;h<N;h++){
          if(D[h]!=-1)continue;
          if(h<=m)S[h]=0;
          else S[h]=1;
        }
        int x=tryCombination(S);
        if(x==-1 || x>i)r=m;
        else l=m+1;
      }
      D[r]=i;
      S[r]=0;
    }
  }
  answer(S,D);
}

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