Submission #784744

#	Time	Username	Problem	Language	Result	Execution time	Memory
784744		bane	Cave (IOI13_cave)	C++17	100 / 100	548 ms	576 KiB

cave

    #include "cave.h"
    #include <bits/stdc++.h>
     
    using namespace std;
    int S[5005], D[5005], st[5005];
    vector<int> u;
    void exploreCave(int N){
       for(int i=0;i<N;i++){
          int t=tryCombination(S);
          bool open=false;
          if(t==i)open=true; // se otvara so drugoto
          int l=-1,r=N-1;
          while(r-l>1){
              int m=(l+r)/2;
              for(int j=0;j<N;j++){
                st[j]=(j<=m?open:!open);
              }
              for(int x:u){
                st[x]=S[x];
              }
              int h=tryCombination(st);
              if(h==i)
                l=m;
              else 
                r=m;
          }
            D[l+1]=i;
            S[l+1]=open;
            u.push_back(l+1);
          
       }
       answer(S,D);
    }

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