Submission #1204627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204627		dzuizz	Cave (IOI13_cave)	C++20	100 / 100	516 ms	512 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
  int S[N],D[N];
  memset(D,-1,sizeof D);
  for(int i=0;i<N;++i){
    for(int j=0;j<N;++j) if(D[j]==-1) S[j]=0;
    int q=tryCombination(S);
    bool k=(q==-1||q>i);
    int l=0,r=N-1,m,ans;
    while(l<=r){
      m=(l+r)>>1;
      for(int j=0;j<N;++j) if(D[j]==-1)
        S[j]=(m<=j&&j<=r?k^1:k);
      int q=tryCombination(S);
      if(q==-1||q>i) ans=m,l=m+1;
      else r=m-1;
    }
    S[ans]=k^1,D[ans]=i;
  }
  answer(S,D);
}

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