#include "minerals.h"
// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i = 0; i < (n); ++i)
#define FOO(i,a,b) for(int i = (a); i <= (b); ++i)
#define AI(x) begin(x),end(x)
template<class I> bool chmax(I &a, I b){ return a < b ? (a = b, true) : false;}
template<class I> bool chmin(I &a, I b){ return a > b ? (a = b, true) : false;}
#ifdef OWO
#define debug(args...) LKJ("[ " + string(#args) + " ]", args)
void LKJ(){ cerr<<endl;}
template<class I, class...T> void LKJ(I&&x, T&&...t){ cerr<<x<<", ", LKJ(t...);}
template<class I> void DE(I a, I b){ while(a < b) cerr<<*a<<" \n"[next(a) == b], ++a;}
#else
#define debug(...) 0
#define DE(...) 0
#endif
void solve(vector<int> &a, vector<int> &b, bool in){
debug("solving:");
DE(AI(a)); DE(AI(b));
assert(a.size() == b.size());
if(a.size() < 1 or b.size() < 1){
return;
}
if(a.size() == 1 and b.size() == 1){
Answer(a[0], b[0]);
return;
}
vector<int> la, lb, ra, rb;
int h = a.size() * 0.38;
for(int i = 0; i < h; ++i) la.pb(a[i]);
for(int i = h; i < a.size(); ++i) lb.pb(a[i]);
int ls, cs;
for(int i: la) cs = Query(i);
for(int i: b){
ls = cs;
cs = Query(i);
if(cs == ls ^ in) ra.pb(i);
else rb.pb(i);
}
DE(AI(la)); DE(AI(lb));
DE(AI(ra)); DE(AI(rb));
solve(la, ra, !in);
solve(lb, rb, in);
}
void Solve(int N) {
vector<int> hulan;
for(int i = 1; i <= N * 2; ++i) hulan.pb(i);
random_shuffle(AI(hulan));
vector<vector<int>> as, bs;
vector<int> a, b;
int ls = 0, cs;
for(int i: hulan){
cs = Query(i);
if(cs == ls) b.pb(i);
else a.pb(i);
if(a.size() == b.size()){
as.pb(a);
bs.pb(b);
a.clear();
b.clear();
}
ls = cs;
}
for(int i = 0; i < as.size(); ++i)
solve(as[i], bs[i], true);
}
Compilation message
minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:22:20: warning: statement has no effect [-Wunused-value]
22 | #define debug(...) 0
| ^
minerals.cpp:27:2: note: in expansion of macro 'debug'
27 | debug("solving:");
| ^~~~~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
23 | #define DE(...) 0
| ^
minerals.cpp:28:2: note: in expansion of macro 'DE'
28 | DE(AI(a)); DE(AI(b));
| ^~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
23 | #define DE(...) 0
| ^
minerals.cpp:28:13: note: in expansion of macro 'DE'
28 | DE(AI(a)); DE(AI(b));
| ^~
minerals.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = h; i < a.size(); ++i) lb.pb(a[i]);
| ~~^~~~~~~~~~
minerals.cpp:49:9: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
49 | if(cs == ls ^ in) ra.pb(i);
| ~~~^~~~~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
23 | #define DE(...) 0
| ^
minerals.cpp:53:2: note: in expansion of macro 'DE'
53 | DE(AI(la)); DE(AI(lb));
| ^~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
23 | #define DE(...) 0
| ^
minerals.cpp:53:14: note: in expansion of macro 'DE'
53 | DE(AI(la)); DE(AI(lb));
| ^~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
23 | #define DE(...) 0
| ^
minerals.cpp:54:2: note: in expansion of macro 'DE'
54 | DE(AI(ra)); DE(AI(rb));
| ^~
minerals.cpp:23:17: warning: statement has no effect [-Wunused-value]
23 | #define DE(...) 0
| ^
minerals.cpp:54:14: note: in expansion of macro 'DE'
54 | DE(AI(ra)); DE(AI(rb));
| ^~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i = 0; i < as.size(); ++i)
| ~~^~~~~~~~~~~
minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:49:9: warning: 'cs' may be used uninitialized in this function [-Wmaybe-uninitialized]
49 | if(cs == ls ^ in) ra.pb(i);
| ~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
141164 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
177 ms |
140652 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
141164 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
141164 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
141164 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
141164 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
141164 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
141164 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
141164 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
