Submission #836226

#	Time	Username	Problem	Language	Result	Execution time	Memory
836226		HollaFoil	Minerals (JOI19_minerals)	C++14	85 / 100	232 ms	68184 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;

int Q(int 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++) {
    bool a = false;
    bool b = false;
    bool c = false;
    if (i >= inserted.first && i <= inserted.second) a = true;
    if (i >= interval.first && i <= interval.second) b = true;
    if (i >= full.first && i <= full.second) c = true;
    if (a != b && c) q = Q(lefts[i]);
  }
}

void search(int i, int j) {
  //cout << "Searching i=" << i << " j=" << j << endl;
  if (i == j) return;
  int a = i;
  int b = (i + j) / 2;
  if (j - i > 30) b = 4*i/10 + 6*j/10;
  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);
  prepareInterval(l, full);
  inserted = l;
  int lcount = b - a + 1;
  int rcount = j - i + 1;
  //cout << "L = (" << a << "; " << b << ")        R = (" << i << "; " << j << ")\n";
  while (!candidates[full].empty()) {
    int c = candidates[full].front();
    candidates[full].pop();
    //cout << "  Candidate " << c << " - ";

    if (lcount == 0) {
      candidates[r].push(c);
      rcount--;
      continue;
    }
    else if (rcount == 0) {
      candidates[l].push(c);
      lcount--;
      continue;
    }
    //cout << " (passed sanity) ";
    int next = Q(c);
    if (q == next) {
      candidates[l].push(c);
      lcount--;
      //cout << " left" << endl;
    }
    else {
      candidates[r].push(c);
      rcount--;
      //cout << " right" << endl;
    }
    q = next;
  }

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

void Solve(int N) {
  InitRand(N);
  pair<int,int> interval = make_pair(0, 2*N-1);
  for (int i = 0; i < 2*N; i++) {
    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);
  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:113:13: warning: unused variable 'i' [-Wunused-variable]
  113 |   for (auto i : lefts) {
      |             ^

• 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: 0 / 5
• Subtask 9: 0 / 10