제출 #309440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
309440		cig32	동굴 (IOI13_cave)	C++14	100 / 100	485 ms	512 KiB

cave

#include "cave.h"
void exploreCave(int N) {
  // TODO: implementation
  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