Submission #112361

#	Time	Username	Problem	Language	Result	Execution time	Memory
112361		shoemakerjo	Minerals (JOI19_minerals)	C++14	100 / 100	95 ms	3440 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;
const int magic = 2;


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) {

    if (a[0] > b[0] || a[1] > b[1]) {
      Answer(a[0], b[1]);
      Answer(a[1], b[0]);
      return;
    }
    if (a[0] > b[1] || a[1] > b[0]) {
      Answer(a[0], b[0]);
      Answer(a[1], b[1]);
      return;
    }


    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;
  for (int i = 0; i < magic; i++) {
    if (mid == 1) break;
    --mid;
  }
  //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;
  vector<int> stuff;
  for (int i = 1; i <= 2*N; i++) {
    stuff.push_back(i);
  }
  shuffle(stuff.begin(), stuff.end(), mt_rand);
  //the above process saves about 2 queries (not worth)

  //beginning has more limitations we are not considering
  for (int i = 1; i <= 2*N; i++) {
    if (cl.size() == N) {
      cr.push_back(i);
      // mbig[i] = i-1;
      continue;
    }
    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:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = mid; i < a.size(); i++) {
                     ~~^~~~~~~~~~
minerals.cpp:89:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < b.size(); i++) {
                   ~~^~~~~~~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:138:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cl.size() == N) {
         ~~~~~~~~~~^~~~

• 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