Submission #1170298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170298		M_W_13	Minerals (JOI19_minerals)	C++20	90 / 100	38 ms	3596 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, bool c) {
  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 pol = szA/2;
  vector<int> A1;
  vector<int> A2;
  vector<int> B1;
  vector<int> B2;
  rep(i, pol) {
    ile = Query(A[i]);
    stan[A[i]] ^= 1;
    A1.pb(A[i]);
  }
  for (int i = pol; i < szA; i++) {
    A2.pb(A[i]);
  }
  bool all2 = false;
  bool all1 = false;
  rep(i, szB) {
    if (all1) {
      B1.pb(B[i]);
      continue;
    }
    else if (all2) {
      B2.pb(B[i]);
      continue;
    }
    int now = Query(B[i]);
    stan[B[i]] ^= 1;
    if (c) {
      if (now == ile) {
        B2.pb(B[i]);
      }
      else {
        B1.pb(B[i]);
      }
    }
    else {
      if (now == ile) {
        B1.pb(B[i]);
      }
      else {
        B2.pb(B[i]);
      }
    }
    ile = now;
    if ((int)B1.size() == (int)A1.size()) {
      all2 = true;
    }
    else if ((int)B2.size() == (int)A2.size()) {
      all1 = true;
    }
  }
  bool c2 = c ^ 1;
  rozw(A1, B1, c2);
  rozw(A2, B2, c);
}

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, true);
}

• 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