#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
#define MAXN 100100
vector<int> a, b;
int a1[MAXN];
vector<int> lo, hi, lo2, hi2;
int blo[MAXN], bhi[MAXN];
int mid, qq, q2;
int took[MAXN];
void Solve(int n)
{
//memset(took, -1, sizeof took);
for (int i = 0; i < 2 * n; i++) {
a1[i] = Query(i + 1);
if (!i || a1[i] != a1[i - 1])
a.pb(i);
else
b.pb(i);
}
//for (int i = 0; i < 2 * n; i++) Query(i + 1);
for (int i = 0; i < n; i++) {
blo[i] = 0;
bhi[i] = n - 1;
}
lo.pb(0); hi.pb(n - 1);
while (1) {
if (lo.size() == 1) {
mid = (lo[0] + hi[0]) / 2;
for (int i = mid + 1; i <= hi[0]; i++) {
qq = Query(a[i] + 1);//cout<<a[i]+1<<'.'<<qq<<endl;
}
}
else {
for (int i = 0; i < lo.size(); i++) {
mid = (lo[i] + hi[i]) / 2;
if (i & 1) {
for (int j = lo[i]; j <= mid; j++)
qq = Query(a[j] + 1);
}
else {
for (int j = mid + 1; j <= hi[i]; j++)
qq = Query(a[j] + 1);
}
}
}
int ok = 0;
for (int i = 0; i < n; i++) {
if (blo[i] >= bhi[i]) {
took[blo[i]] = 1;//cout<<i<<",\n";
continue;
}
if (bhi[i] - blo[i] == 1) {
if (took[bhi[i]]) {//cout<<i<<".\n";
took[blo[i]] = 1;
bhi[i] = blo[i];
continue;
}
if (took[blo[i]]) {
took[bhi[i]] = 1;//cout<<i<<"/\n";
blo[i] = bhi[i];
continue;
}
}
mid = (blo[i] + bhi[i]) / 2;
q2 = Query(b[i] + 1);//cout<<b[i]+1<<','<<q2<<',';
if (qq == q2) {
bhi[i] = mid;
} else {
blo[i] = mid + 1;
}
//cout << blo[i]<<'.'<<bhi[i]<<' ';
if (blo[i] < bhi[i]) ok = 1;
if (blo[i] >= bhi[i]) {//cout<<i<<"!\n";
took[blo[i]] = 1;
continue;
}
qq = q2;
}//cout<<endl;
if (!ok) break;
lo2.clear(); hi2.clear();
for (int i = 0; i < lo.size(); i++) {
mid = (lo[i] + hi[i]) / 2;
lo2.pb(lo[i]);
lo2.pb(mid + 1);
hi2.pb(mid);
hi2.pb(hi[i]);
}
lo = lo2; hi = hi2;
}
for (int i = 0; i < n; i++) {
//cout<<b[i]+1<<' '<<a[blo[i]]+1<<endl;
Answer(b[i] + 1, a[blo[i]] + 1);
}
/*int v = Query(1);
for (int i = 1; i <= N; ++i) {
Answer(i, 2 * N + 1 - i);
}*/
}
Compilation message
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < lo.size(); i++) {
| ~~^~~~~~~~~~~
minerals.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int i = 0; i < lo.size(); i++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
