Submission #1263315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263315		DeltaStruct	Cave (IOI13_cave)	C++20	100 / 100	579 ms	552 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

void exploreCave(int n){
  vector<int> A(n),R(n),B(n,1),D(n);
  auto f = [&n](vector<int>& A) -> int {
    int t = tryCombination(A.data());
    return (t==-1?n:t);
  };
  for (int i(0);i < n;++i){
    A = R; for (int k(0);k < n;++k) if (B[k]) A[k] = 1;
    int t = (f(A)>i),l = 0,r = n,mid;
    while(r-l>1){
      mid = (l+r)/2;
      A = R; for (int k(0);k < n;++k) if (B[k]) A[k] = (l<=k&&k<mid?t:1-t);
      if (f(A)>i) r = mid;
      else l = mid;
    }
    D[l] = i,R[l] = t,B[l] = 0;
  }
  answer(R.data(),D.data());
}

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