Submission #1108165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108165		abczz	Minerals (JOI19_minerals)	C++17	100 / 100	57 ms	34804 KiB

minerals

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

using namespace std;

vector <ll> X, Y;
bool B[100000];
vector <ll> st[1000000];
ll sz, z;
random_device rd;
ll query(ll u) {
  B[u] ^= 1;
  return Query(u);
}
ll M(ll l, ll r) {
  if (l == r) return l;
  return min(r-1, l+(r-l+1)*4/7-1);
}
mt19937 mt(rd());
void solve(ll id, ll l, ll r) {
  if (l == r) {
    Answer(X[l], st[id][0]);
    return;
  }
  ll mid = M(l, r), 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;
  }
  ll xm;
  if (l == mid) {
    Answer(X[l], st[id*2][0]);
  }
  else {
    xm = M(l, mid);
    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]);
  }
  else {
    xm = M(mid+1, r);
    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;
  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=M(0, N-1)+1; i<N; ++i) sz = query(X[i]);
  solve(1, 0, N-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: 10 / 10