Submission #921977

#	Time	Username	Problem	Language	Result	Execution time	Memory
921977		Aiperiii	Cave (IOI13_cave)	C++14	100 / 100	199 ms	756 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;

void exploreCave(int N) {
   int q[N],vis[N],s[N],d[N];
   for(int i=0;i<N;i++){
      q[i]=0;s[i]=0;
      vis[i]=0;d[i]=0;
   }
   for(int i=0;i<N;i++){
      int res1=tryCombination(q);
      if(res1==-1)res1=N;
      if(res1<=i){
         for(int j=0;j<N;j++){
            if(!vis[j]){
               if(q[j]==1)q[j]=0;
               else q[j]=1;
            }
         }
      }
      int l=0,r=N-1;
      while(l<r){
         int md=(l+r)/2;
         for(int j=l;j<=md;j++){
            if(!vis[j]){
               if(q[j]==1)q[j]=0;
               else q[j]=1;
            }
         }
         int res=tryCombination(q);
         if(res==-1)res=N;
         for(int j=l;j<=md;j++){
            if(!vis[j]){
               if(q[j]==1)q[j]=0;
               else q[j]=1;
            }
         }
         if(res>=i+1)l=md+1;
         else r=md;
      }
      vis[r]=1;
      s[r]=q[r];
      d[r]=i;
   }
   answer(s,d);
}

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