Submission #1042254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042254		juicy	Minerals (JOI19_minerals)	C++17	100 / 100	33 ms	4432 KiB

minerals

#include "minerals.h"

#include <bits/stdc++.h>

using namespace std;

template<class T>
ostream &operator << (ostream &os, vector<T> v) {
  cerr << "{";
  for (int i = 0; i < v.size(); ++i) {
    os << (i ? ", " : "") << v[i];
  }
  return os << "}";
}

void __print() {
  cerr << "]\n";
}

template<class T, class... V>
void __print(T t, V... v) {
  cerr << t;
  if (sizeof...(v)) {
    cerr << ", ";
  }
  __print(v...);
}

#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; __print(x);
#else
#define debug(...) 42
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void dc(vector<int> A, vector<int> B, bool flg) {
  if (A.size() == 1) {
    Answer(A[0], B[0]);
    return;
  }
  int L = max(1, int(0.38 * A.size())), R = A.size() - L;
  vector<int> lA, rA, lB, rB;
  int lst = 0;
  for (int i = 0; i < L; ++i) {
    lA.push_back(A[i]);
    lst = Query(A[i]);
  }
  for (int i = L; i < A.size(); ++i) {
    rA.push_back(A[i]);
  }
  for (int x : B) {
    if (lB.size() == L) {
      rB.push_back(x);
      continue;
    } 
    if (rB.size() == R) {
      lB.push_back(x);
      continue;
    }
    int nxt = Query(x);
    if (flg ^ lst != nxt) {
      rB.push_back(x);
    } else {
      lB.push_back(x);
    }
    lst = nxt;
  }
  dc(lA, lB, flg ^ 1);
  dc(rA, rB, flg);
}

void Solve(int N) {
  vector<int> A, B, p(2 * N); iota(p.begin(), p.end(), 1);
  shuffle(p.begin(), p.end(), rng);
  for (int x : p) {
    if (A.size() != Query(x)) {
      A.push_back(x);
    } else {
      B.push_back(x);
    }
  }
  dc(A, B, 1);
}

Compilation message (stderr)

minerals.cpp: In function 'void dc(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = L; i < A.size(); ++i) {
      |                   ~~^~~~~~~~~~
minerals.cpp:53:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     if (lB.size() == L) {
      |         ~~~~~~~~~~^~~~
minerals.cpp:57:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     if (rB.size() == R) {
      |         ~~~~~~~~~~^~~~
minerals.cpp:62:19: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   62 |     if (flg ^ lst != nxt) {
      |               ~~~~^~~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:77:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |     if (A.size() != Query(x)) {
      |         ~~~~~~~~~^~~~~~~~~~~

• 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