Submission #967177

#	Time	Username	Problem	Language	Result	Execution time	Memory
967177		Soumya1	Minerals (JOI19_minerals)	C++17	90 / 100	60 ms	4084 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
int last = 0;
bool ask(int x) {
  int nw = Query(x);
  bool g = (last != nw);
  last = nw;
  return g;
}
void solve(vector<int> a, vector<int> b, bool f) {
  if (a.size() == 1) {
    Answer(a[0], b[0]);
    return;
  }
  int n = a.size();
  int mid = n / 2;
  vector<int> la, lb, ra, rb;
  random_shuffle(a.begin(), a.end());
  random_shuffle(b.begin(), b.end());
  for (int i = 0; i < n; i++) {
    if (i < mid) ask(b[i]), lb.push_back(b[i]);
    else rb.push_back(b[i]);
  }
  for (int i : a) {
    if (la.size() == mid) ra.push_back(i);
    else if (ra.size() == n - mid) la.push_back(i);
    else if (f) {
      if (ask(i)) ra.push_back(i);
      else la.push_back(i);
    } else {
      if (ask(i)) la.push_back(i);
      else ra.push_back(i);
    }
  }
  solve(la, lb, f ^ 1);
  solve(ra, rb, f);
}
void Solve(int N) {
  vector<int> a, b;
  for (int i = 1; i <= 2 * N; i++) {
    if (ask(i)) a.push_back(i);
    else b.push_back(i);
  }
  solve(a, b, 0);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:26:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     if (la.size() == mid) ra.push_back(i);
      |         ~~~~~~~~~~^~~~~~
minerals.cpp:27:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     else if (ra.size() == n - mid) la.push_back(i);
      |              ~~~~~~~~~~^~~~~~~~~~

• 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