Submission #1195377

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

minerals

#include "minerals.h"
#include <vector>

void Solve(int n) {

  int old = Query(1);
  std::vector<int> distinct = {1}, repeated;
  for (int i = 2; i <= 2 * n; ++i) {
    int nval = Query(i);
    if (old != nval) {
      distinct.push_back(i);
    } else {
      repeated.push_back(i);
    }
    old = nval;
  }
  std::vector<int> p(2 * n + 1);
  for (int i = 1; i <= n; ++i) {
    p[i] = distinct[i - 1];
  }
  for (int i = n + 1; i <= 2 * n; ++i) {
    p[i] = repeated[i - n - 1];
  }
  for (int i = 1; i <= 2 * n; ++i) {
    Query(i);
  }
  auto query = [&](int i) {
    return Query(p[i]);
  };
  auto answer = [&](int a, int b) {
    Answer(p[a], p[b]);
  };

  std::vector bit_there(n + 1, std::vector<bool>(15));
  std::vector<std::vector<int>> groups(15);
  for (int i = 1; i <= n; ++i) {
    for (int bt = 0; bt < 15; ++bt) {
      if (i & (1 << bt)) {
        groups[bt].push_back(i);
      }
    }
  }
  for (int bt = 0; bt < 15; ++bt) {
    int old = -1;
    for (auto &i : groups[bt]) {
      old = query(i);
    }
    for (int i = n + 1; i <= 2 * n; ++i) {
      int nval = query(i);
      if (old == nval) {
        bit_there[i - n][bt] = true;
      }
      query(i);
    }
    for (auto &i : groups[bt]) {
      query(i);
    }
  }
  for (int i = 1; i <= n; ++i) {
    int back = 0;
    for (int bt = 0; bt < 15; ++bt) {
      back += (1 << bt) * bit_there[i][bt];
    }
    answer(back, i + n);
  }
}

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