Submission #1195499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195499		avighna	Minerals (JOI19_minerals)	C++20	100 / 100	16 ms	2152 KiB

minerals

#include "minerals.h"
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>

void Solve(int n) {
  int pr = Query(1);
  std::vector<int> set1 = {1}, set2;
  for (int i = 2; i <= 2 * n; ++i) {
    int ne = Query(i);
    (pr != ne ? set1 : set2).push_back(i);
    pr = ne;
  }

  std::random_device rd;
  std::mt19937 rng(rd());
  std::shuffle(set2.begin(), set2.end(), rng);

  // before dnc: set1 == set2
  // make dnc step make it so
  // set1 left half == set2 left half (then set1 right half is automatically ==
  // set2 right half)
  int saved=0;
  auto solve = [&](auto &&self, int l, int r, bool added) {
    if (l == r) {
      Answer(set1[l], set2[l]);
      return;
    }
    int m = l + (r - l) * 0.38;
    // add/remove to/from machine
    for (int i = l; i <= m; ++i) {
      pr = Query(set1[i]);
    }
    int trues = 0, falses = 0;
    std::partition(set2.begin() + l, set2.begin() + r + 1, [&](int x) {
      if (falses >= r - m) {
        saved++;
        trues++;
        return true;
      }
      if (trues >= m - l + 1) {
        saved++;
        falses++;
        return false;
      }
      int ne = Query(x);
      bool unchanged = pr == ne;
      if (added) {
        unchanged = !unchanged; // we actually want it to be changed
      }
      pr = ne;
      trues += unchanged;
      falses += !unchanged;
      return unchanged;
    });
    // do dnc
    self(self, l, m, !added);
    self(self, m + 1, r, added);
  };
  solve(solve, 0, n - 1, true);
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10