#include<minerals.h>
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, a[N];
set<int> slices;
vector<int> le, ri;
vector<ii> answer;
queue<pair<vector<int>, vector<int>>> que;
int arr[N];
bool ck[N];
int co[N];
int cnt[N], tol = 0;
int tot = 0;
/*
int Query(int x){
tot++;
if(!ck[x]){
ck[x] = 1;
if(cnt[co[x]] == 0){
tol++;
}
cnt[co[x]]++;
}
else{
ck[x] = 0;
if(cnt[co[x]] == 1){
tol--;
}
cnt[co[x]]--;
}
return tol;
}
void Answer(int x, int y){
assert(co[x] == co[y]);
assert(x != y);
}*/
void Solve(int N){
n = N;
le.clear();
ri.clear();
slices.clear();
answer.clear();
int lst = 0;
for(int i = 1; i <= 2 * n; i++){
int temp = Query(i);
slices.insert(i);
if(lst < temp){
le.pb(i);
}
else{
ri.pb(i);
}
lst = temp;
}
for(int i = 1; i <= 2 * n; i++) Query(i);
slices.clear();
//vector<int>
que.push({le, ri});
//return;
while(!que.empty()){
vector<int> a = que.front().fi, b = que.front().se;
//cout << a.size() << "\n";
que.pop();
//assert(a.size() == b.size());
if(a.size() == 1){
answer.pb({a[0], b[0]});
continue;
}
int mid = (a.size() + 1) / 2;
vector<int> a1, b1, a2, b2, a3, b3, a4, b4;
for(int i = 0; i < mid; i++){
Query(a[i]);
slices.insert(a[i]);
a1.pb(a[i]);
}
for(int i = mid; i < a.size(); i++) a2.pb(a[i]);
//cout << sum << "\n";
//cout << tol << "\n";
int lst = slices.size();
for(int i = 0; i < b.size(); i++){
int temp = Query(b[i]);
//cout << temp << "\n";
slices.insert(b[i]);
if(temp != lst){
b2.pb(b[i]);
lst = temp;
}
else b1.pb(b[i]);
}
//for(auto it : slices) Query(it);
//slices.clear();
if(a1.size() == 1){
answer.pb({a1[0], b1[0]});
for(auto it : slices) Query(it);
slices.clear();
}
else if(a1.size()){
mid = (a1.size() + 1) / 2;
int lst;
for(int i = 0; i < mid; i++){
lst = Query(a1[i]);
a3.pb(a1[i]);
slices.erase(a1[i]);
}
for(int i = 0; i < b1.size(); i++){
int temp = Query(b1[i]);
slices.erase(b1[i]);
if(temp == lst){
b4.pb(b1[i]);
}
else{
b3.pb(b1[i]);
lst = temp;
}
}
/*
for(int i = mid; i < a1.size(); i++){
a4.pb(a1[i]);
slices.erase(a1[i]);
Query(a1[i]);
}*/
for(auto it : slices) Query(it);
slices.clear();
//assert(tol == 0);
}
//assert(!tol);
if(a3.size()) que.push({a3, b3});
if(a4.size()) que.push({a4, b4});
if(a2.size()) que.push({a2, b2});
}
for(auto it : answer) Answer(it.fi, it.se);
}
/*
void process(){
int x = 38000;
for(int i = 1; i <= x * 2; i++){
co[i] = (i + 1) / 2;
}
Solve(x);
cout << tot << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}*/
Compilation message
minerals.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:101:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i = mid; i < a.size(); i++) a2.pb(a[i]);
| ~~^~~~~~~~~~
minerals.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i = 0; i < b.size(); i++){
| ~~^~~~~~~~~~
minerals.cpp:130:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i = 0; i < b1.size(); i++){
| ~~^~~~~~~~~~~
minerals.cpp:133:5: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
133 | if(temp == lst){
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
328 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
