Submission #1170299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170299		M_W_13	Minerals (JOI19_minerals)	C++20	100 / 100	38 ms	3672 KiB

minerals

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
random_device randek;
mt19937 rng(randek());
const int MAXN = 1e5;
bool stan[MAXN];
int ile = 0;

void rozw(vector<int> A, vector<int> B) {
  shuffle(A.begin(), A.end(), rng);
  shuffle(B.begin(), B.end(), rng);
  int szA = A.size();
  int szB = B.size();
  // cout << szA << " " << szB << '\n';
  if (szA == 0 && szB == 0) {
    return ;
  }
  if (szA == 1 && szB == 1) {
    Answer(A[0], B[0]);
    return ;
  }
  int ile1 = 0;
  int ile2 = 0;
  rep(i, szB) {
    if (stan[B[i]]) {
      ile1++;
    }
    else {
      ile2++;
    }
  }
  int pol = szA/2;
  if (ile1 > pol && szA % 2 == 1) {
    pol++;
  }
  vector<int> A1;
  vector<int> A2;
  rep(i, szB) {
    if (stan[B[i]] && ile1 > pol) {
      ile = Query(B[i]);
      stan[B[i]] = false;
      ile1--;
      ile2++;
    }
    else if ((!stan[B[i]]) && ile1 < pol) {
      ile = Query(B[i]);
      stan[B[i]] = true;
      ile1++;
      ile2--;
    }
    if (stan[B[i]]) {
      A1.pb(B[i]);
    }
    else {
      A2.pb(B[i]);
    }
  }
  vector<int> B1;
  vector<int> B2;
  bool all2 = false;
  bool all1 = false;
  rep(i, szA) {
    if (all1) {
      B1.pb(A[i]);
      continue;
    }
    else if (all2) {
      B2.pb(A[i]);
      continue;
    }
    int now = Query(A[i]);
    stan[A[i]] ^= 1;
    if (now == ile) {
      B1.pb(A[i]);
    }
    else {
      B2.pb(A[i]);
    }
    ile = now;
    if ((int)B1.size() == (int)A1.size()) {
      all2 = true;
    }
    else if ((int)B2.size() == (int)A2.size()) {
      all1 = true;
    }
  }
  rozw(A1, B1);
  rozw(A2, B2);
}

void Solve(int N) {
  rep(i, 2 * N + 2) {
    stan[i] = false;
  }
  vector<int> A;
  vector<int> B;
  bool allb = false;
  for (int v = 1; v <= 2 * N; v++) {
    if (allb) {
      B.pb(v);
      continue;
    }
    int now = Query(v);
    stan[v] = true;
    if (now == ile) {
      B.pb(v);
    }
    else {
      A.pb(v);
    }
    ile = now;
    if ((int)A.size() == N) {
      allb = true;
    }
  }
  // rep(i, N) {
  //   cout << A[i] << " ";
  // }
  // cout << '\n';
  // rep(i, N) {
  //   cout << B[i] << " ";
  // }
  // cout << '\n';
  rozw(A, B);
}

• 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