제출 #1195426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195426		avighna	Minerals (JOI19_minerals)	C++20	0 / 100	0 ms	416 KiB

minerals

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

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<int> set1(n), set2(n);
  std::iota(set1.begin(), set1.end(), 1);
  std::iota(set2.begin(), set2.end(), n + 1);
  // 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)
  auto solve = [&](auto &&self, int l, int r, bool added) {
    if (l == r) {
      answer(set1[l], set2[l]);
      return;
    }
    int m = (l + r) / 2;
    // add to machine
    int p = -1;
    for (int i = l; i <= m and !added; ++i) {
      p = query(set1[i]);
    }
    // now both parts are good
    std::partition(set2.begin() + l, set2.begin() + r + 1, [&](int x) {
      int n = query(x);
      bool unchanged = p == n;
      p = n;
      return unchanged;
    });
    // do dnc
    self(self, l, m, true);
    self(self, m + 1, r, false);
  };
  solve(solve, 0, n - 1, false);
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 25
• Subtask 3: 0 / 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