Submission #200916

#	Time	Username	Problem	Language	Result	Execution time	Memory
200916		EntityIT	Minerals (JOI19_minerals)	C++14	40 / 100	38 ms	2232 KiB

minerals

#include "minerals.h"
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

int n;
vector<int> part[2];

int prv = 0;
bool query(int x) {
  int cur = Query(x);
  bool ret = (cur != prv);
  prv = cur;
  return ret;
}

void solve(int Left, int Right, const vector<int> &candidate) {
  if (Left == Right) {
    Answer(part[0][Left], candidate[0] );
    return ;
  }

  int Mid = (Left + Right) >> 1;
  vector<int> nCandidate[2];
  for (int i = Mid + 1; i <= Right; ++i) query(part[0][i]);
  for (auto i : candidate) nCandidate[query(i)].emplace_back(i);
  solve(Left, Mid, nCandidate[0]);

  for (int i = Left; i <= Right; ++i) query(part[0][i]);
  solve(Mid + 1, Right, nCandidate[1]);
}

void Solve(int N) {
  n = N;
  for (int i = 1; i <= n << 1; ++i) part[query(i)].emplace_back(i);

  solve(0, n - 1, part[1]);
}

• 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