Submission #112356

#	Time	Username	Problem	Language	Result	Execution time	Memory
112356		shoemakerjo	Minerals (JOI19_minerals)	C++14	40 / 100	284 ms	6108 KiB

minerals

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

using namespace std;

int nmask[45000];
map<int, int> v;

map<int, int> ccount;

mt19937 mt_rand(time(NULL));

void Solve(int N) {
  // int nrounds = 1000000/N;
  int pguy = 0;

  //throw me out if I am completely alone in my mask

  set<int> curin;
  vector<int> stuff;
  for (int i = 1; i <= 2*N; i++) {
    curin.insert(i);
  }
  int nc = 0;
  int pres = 0;
  while (curin.size()) {
    ++nc;
    stuff.clear();
    for (int v : curin) {
      stuff.push_back(v);
    }
    shuffle(stuff.begin(), stuff.end(), mt_rand);
    ccount.clear();
    v.clear();
    for (int vv : stuff) {
      nmask[vv] *= 2;
      int cur = Query(vv);
      if (cur != pres) {
        nmask[vv]++;
        pres = cur;
      }
      ccount[nmask[vv]]++;
      v[nmask[vv]] = vv;

      // cout << vv << " : " << nmask[vv] << endl;
    }

    for (int vv : stuff) {
      if (ccount[nmask[vv]] > 1) continue;
      int omask =  nmask[vv] ^ ((1 << nc)-1);
      if (nmask[vv] < omask) continue;
      int og = v[omask];
      // cout << vv << " and " << og << endl;
      Answer(vv, og);
      curin.erase(curin.find(vv));
      curin.erase(curin.find(og));
    }
  }
}

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:15:7: warning: unused variable 'pguy' [-Wunused-variable]
   int pguy = 0;
       ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10