Submission #1108065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108065		abczz	Minerals (JOI19_minerals)	C++17	90 / 100	58 ms	21760 KiB

minerals

#include "minerals.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#define ll long long 

using namespace std;

vector <ll> X, Y;
bool B[100000];
vector <ll> st[400000];
ll sz, z;
random_device rd;
ll query(ll u) {
  B[u] ^= 1;
  return Query(u);
}
mt19937 mt(rd());
void solve(ll id, ll l, ll r) {
  if (l == r) {
    Answer(X[l], st[id][0]);
    return;
  }
  ll mid = (l+r)/2, a = 0, b = 0;
  shuffle(st[id].begin(), st[id].end(), mt);
  for (auto u : st[id]) {
    if (a == mid-l+1) {
      st[id*2+1].push_back(u);
      continue;
    }
    else if (b == r-mid) {
      st[id*2].push_back(u);
      continue;
    }
    z = query(u);
    if (sz == z) st[id*2].push_back(u), ++a;
    else st[id*2+1].push_back(u), ++b;
    sz = z;
  }
  if (l == mid) {
    Answer(X[l], st[id*2][0]);
  }
  else {
    ll xm = (l+mid)/2;
    for (int i=l; i<=xm; ++i) if (!B[X[i]]) sz = query(X[i]);
    for (int i=xm+1; i<=mid; ++i) if (B[X[i]]) sz = query(X[i]);
    solve(id*2, l, mid);
  }
  if (mid+1 == r) {
    Answer(X[r], st[id*2+1][0]);
    return;
  }
  ll xm = (mid+1+r)/2;
  sort(st[id*2+1].begin(), st[id*2+1].end(), [](auto a, auto b) {
    return B[a] > B[b];
  });
  for (int i=mid+1; i<=r; ++i) {
    swap(X[i], st[id*2+1][i-mid-1]);
  }
  for (int i=mid+1; i<=xm; ++i) if (!B[X[i]]) sz = query(X[i]);
  for (int i=xm+1; i<=r; ++i) if (B[X[i]]) sz = query(X[i]);
  solve(id*2+1, mid+1, r);
}

void Solve(int N) {
  sz = 0;
  ll tot = N;
  vector <ll> V;
  for (int i=1; i<=2*N; ++i) {
    V.push_back(i);
  }
  for (int i=1; i<=2*N; ++i) {
    z = query(i);
    if (sz != z) X.push_back(i);
    else Y.push_back(i);
    sz = z;
  }
  shuffle(X.begin(), X.end(), mt);
  shuffle(Y.begin(), Y.end(), mt);
  for (auto u : Y) st[1].push_back(u);
  for (int i=(N-1)/2+1; i<N; ++i) sz = query(X[i]);
  solve(1, 0, tot-1);
}

• 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: 0 / 10