Submission #1180212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180212		kunzaZa183	Cave (IOI13_cave)	C++20	100 / 100	131 ms	612 KiB

cave

#include "cave.h"

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

void exploreCave(int N) {
  vector<int> left, det;
  int *corr = new int[N], *linkto = new int[N];
  for (int i = 0; i < N; i++) left.push_back(i);
  int *qry = new int[N];
  for (int i = 0; i < N; i++) {
    fill(qry, qry + N, 0);

    for (auto a : det) qry[a] = corr[a];

    int x = tryCombination(qry);
    if (x == -1) {
      x = N;
    }

    int pos = -1;
    if (x > i) {
      pos = 0;
    } else
      pos = 1;

    int l = 0, r = left.size() - 1;
    while (l < r) {
      int mid = (l + r) / 2;
      for (int i = l; i <= mid; i++) qry[left[i]] = pos;
      for (int i = mid + 1; i <= r; i++) qry[left[i]] = 1 - pos;

      x = tryCombination(qry);
      if (x == -1) {
        x = N;
      }

      if (x > i) {
        r = mid;
      } else
        l = mid + 1;
    }

    linkto[left[l]] = i;
    corr[left[l]] = pos;

    det.push_back(left[l]);
    left.erase(left.begin() + l);
  }

  answer(corr, linkto);
}

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