Submission #1221067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221067		hmms127	Cave (IOI13_cave)	C++20	100 / 100	395 ms	516 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define f2(m,n) for(int i=m;i<n;i++)
#define f4(m,n) for(int j=m;j<n;j++)
void exploreCave(int N){	
   int sw[N]={},dr[N]={};
   bool vis[N]={};
   f2(0,N){
      f4(0,N)if(!vis[j])sw[j]=0;
      int x=tryCombination(sw);
      bool bt=(x==i ? 1:0);
      int l=0,r=N-1,ans=0;
      while(l<r){
          int mid=(l+r)/2;
          f4(0,N){
              if(!vis[j]){
                  if(j<=mid)sw[j]=bt;
                  else sw[j]=bt^1;
              }
          }
          int x=tryCombination(sw); 
          if(x==i)ans=mid+1,l=mid+1;
          else r=mid;
      }
      vis[ans]=1;
      sw[ans]=bt;
      dr[ans]=i;
   }
   answer(sw,dr);
   return;
}

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