Submission #923764

#	Time	Username	Problem	Language	Result	Execution time	Memory
923764		artixkrishna	Cave (IOI13_cave)	C++14	100 / 100	201 ms	852 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