Submission #476351

#	Time	Username	Problem	Language	Result	Execution time	Memory
476351		ponytail	Cave (IOI13_cave)	C++17	100 / 100	362 ms	456 KiB

cave

#include<bits/stdc++.h>
#include "cave.h"

using namespace std;


void exploreCave(int N) {
    int S[N],D[N];
  bool solved[N];
  for(int i=0;i<N;i++){
      solved[i]=false;
      D[i]=-1;
  }
  for(int i=0;i<N;i++){
      int candidates[N];
      int ppt=0;
      for(int j=0;j<N;j++){
          if(solved[j]==false){
              S[j]=0;
              candidates[ppt]=j;
              ppt++;
          }
      }
      int lb=0, rb=ppt-1;
      int res=tryCombination(S);
      int opt=(res==i?1:0);
      for(int j=0;j<N;j++){
          if(solved[j]==false){
              S[j]=1-opt;
          }
      }
      res=tryCombination(S);
      while(lb<rb){
          int mid=(lb+rb)/2;
          for(int j=lb;j<=mid;j++){
              if(solved[candidates[j]])continue;
              S[candidates[j]]=1-S[candidates[j]];
          }
          int now=tryCombination(S);
          for(int j=lb;j<=mid;j++){
              if(solved[candidates[j]])continue;
              S[candidates[j]]=1-S[candidates[j]];
          }
          if(now!=res){
              rb=mid;
          }
          else{
              lb=mid+1;
          }
      }
      solved[candidates[lb]]=true;
      S[candidates[lb]]=opt;
      D[candidates[lb]]=i;
  }
  answer(S,D);
}

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