#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
struct RNG {
int operator () (int n) {
return rnd(n);
}
};
void scattered(vector<int> u, vector<int> v, int f) {
if(u.empty()) return;
if(u.size() == 1) {
Answer(u.back(), v.back());
return;
}
random_shuffle(u.begin(), u.end(), RNG());
// random_shuffle(v.begin(), v.end(), RNG());
int mid = ((int)u.size() - 2) >> 1;
int last;
if(f) {
for(int i = mid + 1; i < v.size(); i++) {
last = Query(v[i]);
}
} else {
for(int i = 0; i <= mid; i++) {
last = Query(v[i]);
}
}
vector<int> lu, lv(v.begin(), v.begin() + mid + 1), ru, rv(v.begin() + mid + 1, v.end());
for(int i = 0; i < u.size(); i++) {
if(lu.size() == lv.size()) {
ru.emplace_back(u[i]);
} else if(ru.size() == rv.size()) {
lu.emplace_back(u[i]);
} else {
int rep = Query(u[i]);
if(rep == last) {
lu.emplace_back(u[i]);
} else {
ru.emplace_back(u[i]);
}
last = rep;
}
}
scattered(lu, lv, 1);
scattered(ru, rv, 0);
}
void together(vector<int> v) {
random_shuffle(v.begin(), v.end(), RNG());
if(v.empty()) return;
if(v.size() == 2) return Answer(v[0], v[1]);
if(v.size() == 4) {
int last = Query(v[0]);
if(Query(v[1]) == last) {
together({v[0], v[1]});
together({v[2], v[3]});
return;
} else {
scattered({v[2], v[3]}, {v[0], v[1]}, 1);
}
return;
}
if(v.size() == 6) {
return;
}
int mid = ((int)v.size()) / 2 - 1;
vector<int> l, r, dl, dr;
int last = 0;
for(int i = 0; i <= mid; i++) {
int rep = Query(v[i]);
if(rep == last) {
l.emplace_back(v[i]);
}
last = rep;
}
for(int i = 0; i <= mid; i++) {
int rep = Query(v[i]);
if(rep == last) {
l.emplace_back(v[i]);
}
last = rep;
}
last = 0;
for(int i = mid + 1; i < v.size(); i++) {
int rep = Query(v[i]);
if(rep == last) {
r.emplace_back(v[i]);
}
last = rep;
}
for(int i = mid + 1; i < v.size(); i++) {
int rep = Query(v[i]);
if(rep == last) {
r.emplace_back(v[i]);
}
last = rep;
}
set<int> sl(l.begin(), l.end()), sr(r.begin(), r.end());
for(int i = 0; i <= mid; i++) {
if(sl.find(v[i]) == sl.end()) {
dl.emplace_back(v[i]);
}
}
for(int i = mid + 1; i < v.size(); i++) {
if(sr.find(v[i]) == sr.end()) {
dr.emplace_back(v[i]);
}
}
together(l);
together(r);
scattered(dl, dr, 0);
}
void Solve(int N) {
vector<int> v(2 * N);
iota(v.begin(), v.end(), 1);
together(v);
}
Compilation message
minerals.cpp: In function 'void scattered(std::vector<int>, std::vector<int>, int)':
minerals.cpp:25:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = mid + 1; i < v.size(); i++) {
~~^~~~~~~~~~
minerals.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < u.size(); i++) {
~~^~~~~~~~~~
minerals.cpp: In function 'void together(std::vector<int>)':
minerals.cpp:93:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = mid + 1; i < v.size(); i++) {
~~^~~~~~~~~~
minerals.cpp:100:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = mid + 1; i < v.size(); i++) {
~~^~~~~~~~~~
minerals.cpp:113:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = mid + 1; i < v.size(); i++) {
~~^~~~~~~~~~
minerals.cpp: In function 'void scattered(std::vector<int>, std::vector<int>, int)':
minerals.cpp:41:4: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(rep == last) {
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
