Submission #836266

#	Time	Username	Problem	Language	Result	Execution time	Memory
836266		HollaFoil	Minerals (JOI19_minerals)	C++14	0 / 100	3 ms	2000 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> m;
unordered_map<int, int> unm;
map<pair<int,int>, queue<int>> candidates;
unordered_map<int, bool> ins;

int Q(int i) {
  ins[i] = !ins[i];
  return Query(m[i]+1);
}

void InitRand(int N) {
  srand(7);
  vector<int> order(2*N);
  for (int i = 0; i < 2*N; i++) order[i]=i;
  random_shuffle(order.begin(), order.end());
  random_shuffle(order.begin(), order.end());
  for (int i = 0; i < 2*N; i++) {
    m[i]=order[i];
    unm[order[i]]=i;
    //m[i] = i;
  }
}

pair<int,int> inserted;
vector<int> lefts;
int q = -1;

void prepareInterval(pair<int,int> interval, pair<int, int> full) {
  //cout << "Preparing intervals: " << "in - (" << inserted.first << "; " << inserted.second << ")  target - (" << interval.first << "; " << interval.second << ")\n";
  for (int i = full.first; i <= full.second; i++) {
    if (i >= interval.first && i <= interval.second) {
      if (!ins[i]) Q(i);
    }
    else if (ins[i]) Q(i);
  }
}

void search(int i, int j,bool thing) {
  //cout << "Searching i=" << i << " j=" << j << endl;
  if (i == j) return;
  int a = i;
  int diff = j - i + 1;
  int mid;
  if (thing) mid = (diff*2)/3;
  else mid = (diff+2)/3;

  int b = a + mid - 1;
  i = b+1;

  pair<int, int> full = make_pair(a, j);
  pair<int, int> l = make_pair(a, b);
  pair<int, int> r = make_pair(i, j);

  if (thing) prepareInterval(r, full);
  else prepareInterval(l, full);
  if (thing) inserted = r;
  else inserted = l;
  int lcount = b - a + 1;
  int rcount = j - i + 1;
  while (!candidates[full].empty()) {
    int c = candidates[full].front();
    candidates[full].pop();

    if (lcount == 0) {
      candidates[r].push(c);
      rcount--;
      continue;
    }
    else if (rcount == 0) {
      candidates[l].push(c);
      lcount--;
      continue;
    }
    int next = Q(c);
    if (thing) {
      if (q == next) {
        candidates[r].push(c);
        rcount--;
      }
      else {
        candidates[l].push(c);
        lcount--;
      }
    }
    else {
      if (q == next) {
        candidates[l].push(c);
        lcount--;
      }
      else {
        candidates[r].push(c);
        rcount--;
      }
    }
    q = next;
  }

  search(a, b, true);
  search(i, j, false);
}

void Solve(int N) {
  InitRand(N);
  pair<int,int> interval = make_pair(0, 2*N-1);
  for (int i = 0; i < 2*N; i++) {
    ins[i] = false;
    candidates[interval].push(i);
  }
  interval = make_pair(0, N-1);
  q = Q(0);
  lefts.push_back(0);
  for (int i = 1; i < 2*N; i++) {
    int next = Q(i);
    if (q == next) {
      candidates[interval].push(i);
    }
    else {
      q = next;
      lefts.push_back(i);
    }
  }
  inserted = make_pair(0, N-1);
  //cout << "Left: ";
  for (auto i : lefts) {
    //cout << i << " ";
  }

  search(0, N-1, true);
  for (int i = 0; i < N; i++) {
    int a = m[lefts[i]];
    int b = m[candidates[make_pair(i, i)].front()];
    //cout << a << " = " << b << endl;
    Answer(a+1, b+1);
  }


}
/*

4
0 4
1 5
2 3
6 7

*/

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:128:13: warning: unused variable 'i' [-Wunused-variable]
  128 |   for (auto i : lefts) {
      |             ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 25
• Subtask 3: 0 / 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