Submission #1308436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308436		KickingKun	Minerals (JOI19_minerals)	C++20	40 / 100	26 ms	4088 KiB

minerals

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

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int random(int l, int r) {
  return uniform_int_distribution <int> (l, r)(rng);
}

#define pii pair <int, int>
#define fi first
#define se second

const int MAXN = 50000;
vector <int> events[MAXN];

void Solve(int N) {
  vector <int> L, R;
  for (int i = 1; i <= 2 * N; i++) {
    if (Query(i) == L.size() + 1) L.emplace_back(i);
    else {
      Query(i);
      R.emplace_back(i);
    }
  }
  for (int &x: L) Query(x);

  vector <pii> range(N, make_pair(0, N - 1));
  vector <bool> remove(N);

  while (true) {
    for (int i = 0; i < N; i++) {
      if (range[i].fi == range[i].se) {
        remove[range[i].fi] = true;
      }
    }

    vector <int> remain;
    for (int i = 0; i < N; i++)
      if (!remove[i]) remain.emplace_back(i);
    if (remain.empty()) break;

    // cerr << remain.size() << endl;

    for (int i = 0; i < remain.size(); i++)
      events[i].clear();

    int maId = -1;
    for (int i = 0; i < N; i++) if (range[i].fi != range[i].se) {
      int l = lower_bound(remain.begin(), remain.end(), range[i].fi) - remain.begin();
      int r = upper_bound(remain.begin(), remain.end(), range[i].se) - remain.begin() - 1;
      if (range[i].fi == range[i].se) range[i].fi = range[i].se = remain[l];
      else {
        range[i] = make_pair(remain[l], remain[r]);
        int mid = (l + r) >> 1;
        events[mid].emplace_back(i);
        maId = max(maId, mid);
      }
    }
    if (maId == -1) break;

    for (int i = 0; i <= maId; i++) {
      Query(R[remain[i]]);
      for (int &l: events[i]) {
        int tmp = Query(L[l]); Query(L[l]);
        if (tmp == i + 1) range[l].se = remain[i];
        else range[l].fi = remain[i + 1];
      }
    }
    for (int i = 0; i <= maId; i++) Query(R[remain[i]]);
  }

  for (int i = 0; i < N; i++)
    Answer(L[i], R[range[i].fi]);
}

• 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