#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 diff = j - i + 1;
int a = i;
int b = a + (diff*10)/33;
if (diff < 30) b = a + diff/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, 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
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:114:13: warning: unused variable 'i' [-Wunused-variable]
114 | for (auto i : lefts) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
138 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
