Submission #112357

#	Time	Username	Problem	Language	Result	Execution time	Memory
112357		shoemakerjo	Minerals (JOI19_minerals)	C++14	40 / 100	315 ms	12396 KiB

minerals

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

using namespace std;
using ll = long long;

const int maxn = 100010;
ll nmask[maxn];
map<ll, int> v;

map<ll, int> ccount;
vector<int> csame[maxn];

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();
    v.clear();

    if (nc == 0) {
      for (int i = 1; i <= 2*N; i++) {
        stuff.push_back(i);
      }
      shuffle(stuff.begin(), stuff.end(), mt_rand);
    }
    else {
      for (int vv : curin) {
        // stuff.push_back(v);
        csame[vv].clear();
        if (v.count(nmask[vv])) {
          csame[v[nmask[vv]]].push_back(vv);
        }
        else {
          v[nmask[vv]] = vv;
          // csame[vv].clear();
          csame[vv].push_back(vv);
        }
      }
      for (int vv : curin) {
        if (csame[vv].size() == 0) continue;
        int omask = nmask[vv] ^ ((1 << nc) - 1);
        if (omask > nmask[vv]) continue;
        shuffle(csame[vv].begin(), csame[vv].end(), mt_rand);
        int og = v[omask];
        shuffle(csame[og].begin(), csame[og].end(), mt_rand);
        for (int i = 0; i < csame[vv].size(); i++) {
          stuff.push_back(csame[vv][i]);
          stuff.push_back(csame[og][i]);
        }
      }
    }
    // shuffle(stuff.begin(), stuff.end(), mt_rand);
    ccount.clear();
    v.clear();
    for (int vv : stuff) {
      nmask[vv] *= 2LL;
      int cur = Query(vv);
      if (cur != pres) {
        nmask[vv]++;
        pres = cur;
      }
      ccount[nmask[vv]]++;
      v[nmask[vv]] = vv;
      // cout << vv << " : " << nmask[vv] << endl;
    }
    ++nc;
    for (int vv : stuff) {
      if (ccount[nmask[vv]] > 1) continue;
      ll omask =  nmask[vv] ^ ((1LL << 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:60:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < csame[vv].size(); i++) {
                         ~~^~~~~~~~~~~~~~~~~~
minerals.cpp:18: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