#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "swaps.h"
const int MAX_N = 300010;
void solve(int N, int V) {
int sz = 1;
while (sz < N) sz <<= 1;
vector<int> id(sz); iota(AI(id), 1);
random_shuffle(AI(id));
random_shuffle(AI(id));
vector<pair<int,int>> comp, ext;
auto add_cp = [&](int i, int j) {
if (max(id[i], id[j]) > N) {
ext.pb(i, j);
return;
}
schedule(id[i], id[j]);
comp.pb(i, j);
};
auto done = [&]() {
vector<int> ret = visit();
for (int j = 0;j < ret.size();++j) {
if (ret[j] == 0) {
auto [x, y] = comp[j];
DE(id[x], id[y]);
swap(id[x], id[y]);
}
}
for (auto [i, j] : ext) {
if (id[i] > N) {
swap(id[i], id[j]);
}
}
ext.clear();
comp.clear();
};
for (int d = sz/2;d > 0;d >>= 1) {
for (int i = 0;i < sz;++i) if (i&d)
add_cp(i-d, i);
done();
DE(d);
debug(AI(id));
}
DE("sort back");
for (int d = 2;d <= sz;d <<= 1) {
for (int i = 0;i < sz;i += d) {
for (int j = 1;j < d/2;++j) {
DE(i+j, i+d/2+j-1);
add_cp(i+j, i+d/2+j-1);
}
}
done();
for (int i = 0;i < sz;i += d) {
vector<int> nod {id[i]};
for (int j = 1;j < d/2;++j) {
nod.pb(id[i+j]);
nod.pb(id[i+d/2+j-1]);
}
nod.pb(id[i+d-1]);
for (int j = 0;j < d;++j)
id[i + j] = nod[j];
}
DE(d);
debug(AI(id));
}
id.resize(N);
answer(id);
}
Compilation message
swaps.cpp: In lambda function:
swaps.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int j = 0;j < ret.size();++j) {
| ~~^~~~~~~~~~~~
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
swaps.cpp:46:5: note: in expansion of macro 'DE'
46 | DE(id[x], id[y]);
| ^~
swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
swaps.cpp:63:3: note: in expansion of macro 'DE'
63 | DE(d);
| ^~
swaps.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
swaps.cpp:64:3: note: in expansion of macro 'debug'
64 | debug(AI(id));
| ^~~~~
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
swaps.cpp:66:2: note: in expansion of macro 'DE'
66 | DE("sort back");
| ^~
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
swaps.cpp:70:5: note: in expansion of macro 'DE'
70 | DE(i+j, i+d/2+j-1);
| ^~
swaps.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
swaps.cpp:85:3: note: in expansion of macro 'DE'
85 | DE(d);
| ^~
swaps.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
swaps.cpp:86:3: note: in expansion of macro 'debug'
86 | debug(AI(id));
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
