Submission #112359

#	Time	Username	Problem	Language	Result	Execution time	Memory
112359		shoemakerjo	Minerals (JOI19_minerals)	C++14	90 / 100	86 ms	2932 KiB

minerals

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

using namespace std;
using ll = long long;

const int maxn = 100010;
// map<ll, int> v;

mt19937 mt_rand(time(NULL));

int cval;

void go(vector<int>& a, vector<int>& b, bool aactive) {

  // cout << "as: ";
  // for (int vv : a) cout << vv << " ";
  // cout << endl;
  // cout << "bs: ";
  // for (int vv : b) cout << vv << " ";
  // cout << endl;

  if (a.size() == 2) {
    cval = Query(a[0]);
    int cur = Query(b[0]);
    if (aactive) {
      if (cval == cur) {
        Answer(a[0], b[1]);
        Answer(a[1], b[0]);
      }
      else {
        Answer(a[0], b[0]);
        Answer(a[1], b[1]);
      }
    }
    else {
      if (cval == cur) {
        Answer(a[0], b[0]);
        Answer(a[1], b[1]);
      }
      else {
        Answer(a[0], b[1]);
        Answer(a[1], b[0]);
      }
    }
    cval = cur;
    return;
  }

  vector<int> al, bl, ar, br;
  shuffle(a.begin(), a.end(), mt_rand);
  shuffle(b.begin(), b.end(), mt_rand);
  if (a.size() == 1 && b.size() == 1) {
    Answer(a[0], b[0]);
    return;
  }
  if (a.size() == 0) return;

  int mid = a.size()/2;
  //modify what is true for all less than this
  for (int i = 0; i < mid; i++) {
    cval = Query(a[i]);
    al.push_back(a[i]);
  }
  for (int i = mid; i < a.size(); i++) {
    ar.push_back(a[i]);
  }

  for (int i = 0; i < b.size(); i++) {
    // cout << "here: " << b[i] << endl;
    if (bl.size() == al.size()) {
      br.push_back(b[i]);
      continue;
    }
    if (br.size() == ar.size()) {
      bl.push_back(b[i]);
      continue;
    }

    int cur = Query(b[i]);
    if (cur != cval) {
      if (aactive) {
        bl.push_back(b[i]);
      }
      else {
        br.push_back(b[i]);
      }
    }
    else {
      if (aactive) {
        br.push_back(b[i]);
      }
      else {
        bl.push_back(b[i]);
      }
    }
    cval = cur;
  }

  go(al, bl, !aactive);
  go(ar, br, aactive);

}

void Solve(int N) {
  // int nrounds = 1000000/N;
  vector<int> cl, cr;
  cval = 0;
  for (int i = 1; i <= 2*N; i++) {
    int cur = Query(i);
    if (cur == cval) {
      cl.push_back(i);
    }
    else cr.push_back(i);
    cval = cur;
  }
  go(cl, cr, true);
}

Compilation message (stderr)

minerals.cpp: In function 'void go(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = mid; i < a.size(); i++) {
                     ~~^~~~~~~~~~
minerals.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < b.size(); 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