#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int query(int x) {
return Query(x+1);
}
void Solve(int n) {
vector<int> in(2*n), c(2*n);
vector<int> f,s;
int last=0;
vector<int> p; forn(i,2*n) p.pb(i);
shuffle(p.begin(),p.end(),rng);
forn(i,2*n) {
if (last==n) {
s.pb(p[i]); continue;
}
int z = query(p[i]);
if (z > last) f.pb(p[i]);
else s.pb(p[i]);
in[p[i]]=1;
last = z;
}
forn(i,n) c[f[i]]=i;
vector<pi> v(n);
forn(i,n) v[i]={0,n-1};
multiset<int> st;
forn(i,n) st.insert(n/2);
vector<vector<int>> ok(n);
forn(i,n) ok[n/2].pb(i);
set<int> alive;
forn(i,n) alive.insert(i);
vector<vector<int>> other(n);
int dir = -1;
int pos = n-1;
int q2=0, q3=0;
while (st.size()) {
++q2;
//cout<<pos<<' '<<dir<<'\n';
//for(auto&x:st) cout<<x<<' '; cout<<'\n';
//for(auto&x:alive) cout<<x<<' '; cout<<'\n';
//cout<<'\n';
//cout.flush();
if (dir == 1) {
vector<int> lq,rq;
for(auto&x:ok[pos]) {
st.erase(st.find(pos));
int l=v[x].f, r=v[x].s;
assert(l!=r);
int m=(l+r+1)>>1;
if (lq.size() == m-l) {
rq.pb(x); continue;
}
if (rq.size() == r-m+1) {
lq.pb(x); continue;
}
int q = query(s[x]); q3++;
if (q != last) {
rq.pb(x);
} else {
lq.pb(x);
}
in[s[x]]^=1;
last = q;
}
ok[pos].clear();
for(auto&x:lq) {
int l=v[x].f, r=v[x].s;
int m=(l+r+1)>>1;
r=m-1;
v[x] = {l,r};
if (l==r) {
alive.erase(x);
} else {
st.insert(m);
ok[m].pb(x);
}
}
for(auto&x:rq) {
int l=v[x].f, r=v[x].s;
int m=(l+r+1)>>1;
l=m;
v[x] = {l,r};
if (l==r) {
alive.erase(x);
} else {
st.insert(m);
ok[m].pb(x);
}
}
auto it = st.lower_bound(pos);
if (it==st.end()) {
dir*=-1;
continue;
}
if (alive.count(pos)) last = query(f[pos]);
++pos;
} else {
auto it3 = st.upper_bound(pos);
if (it3!=st.end()) {
auto it2 = alive.upper_bound(pos);
pos = *it2;
dir *= -1; continue;
}
if (alive.count(pos)) last = query(f[pos]);
vector<int> lq,rq;
for(auto&x:ok[pos]) {
st.erase(st.find(pos));
int l=v[x].f, r=v[x].s;
assert(l!=r);
int m=(l+r+1)>>1;
if (lq.size() == m-l) {
rq.pb(x); continue;
}
if (rq.size() == r-m+1) {
lq.pb(x); continue;
}
int q = query(s[x]); q3++;
if (q != last) {
l = m;
rq.pb(x);
} else {
r = m-1;
lq.pb(x);
}
in[s[x]]^=1;
last = q;
}
ok[pos].clear();
for(auto&x:lq) {
int l=v[x].f, r=v[x].s;
int m=(l+r+1)>>1;
r=m-1;
v[x] = {l,r};
if (l==r) {
alive.erase(x);
} else {
st.insert(m);
ok[m].pb(x);
}
}
for(auto&x:rq) {
int l=v[x].f, r=v[x].s;
int m=(l+r+1)>>1;
l=m;
v[x] = {l,r};
if (l==r) {
alive.erase(x);
} else {
st.insert(m);
ok[m].pb(x);
}
}
auto it = st.lower_bound(pos);
if (it == st.begin()) {
dir *= -1;
continue;
}
--pos;
}
}
//cout<<"? "<<q2<<' '<<q3<<" ";
forn(i,n) Answer(s[i]+1,f[v[i].f]+1);
}
Compilation message
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:68:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
68 | if (lq.size() == m-l) {
| ~~~~~~~~~~^~~~~~
minerals.cpp:71:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
71 | if (rq.size() == r-m+1) {
| ~~~~~~~~~~^~~~~~~~
minerals.cpp:135:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
135 | if (lq.size() == m-l) {
| ~~~~~~~~~~^~~~~~
minerals.cpp:138:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
138 | if (rq.size() == r-m+1) {
| ~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
