#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> m;
unordered_map<int, int> unm;
map<pair<int,int>, unordered_set<int>> candidates;
int Q(int i) {
return Query(m[i]+1);
}
void InitRand(int N) {
srand(5);
vector<int> order(2*N);
for (int i = 0; i < 2*N; i++) order[i]=i;
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) {
//cout << "Preparing intervals: " << "in - (" << inserted.first << "; " << inserted.second << ") target - (" << interval.first << "; " << interval.second << ")\n";
for (int i = min(inserted.first, interval.first); i <= max(inserted.second, interval.second); i++) {
bool a = false;
bool b = false;
if (i >= inserted.first && i <= inserted.second) a = true;
if (i >= interval.first && i <= interval.second) b = true;
if (a != b) 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;
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);
inserted = l;
int lcount = b - a + 1;
int rcount = j - i + 1;
//cout << "L = (" << a << "; " << b << ") R = (" << i << "; " << j << ")\n";
for (auto candidate : candidates[full]) {
int c = candidate;
//cout << " Candidate " << c << " - ";
if (lcount == 0) {
candidates[r].insert(c);
rcount--;
continue;
}
else if (rcount == 0) {
candidates[l].insert(c);
lcount--;
continue;
}
//cout << " (passed sanity) ";
int next = Q(c);
if (q == next) {
candidates[l].insert(c);
lcount--;
//cout << " left" << endl;
}
else {
candidates[r].insert(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].insert(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].insert(i);
}
else {
q = next;
lefts.push_back(i);
}
}
inserted = make_pair(0, N-1);
//cout << "Left: ";
for (auto i : lefts) {
//cout << i << " ";
}
//cout << endl << "Candidates: ";
for (auto c : candidates[interval]) {
//cout << c << " ";
}
//cout << endl;
search(0, N-1);
for (int i = 0; i < N; i++) {
int a = m[lefts[i]];
int b = m[*(candidates[make_pair(i, i)].begin())];
//cout << a << " = " << b << endl;
Answer(a+1, b+1);
}
}
/*
4
0 4
1 5
2 3
6 7
*/
