//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
// swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> net;
int recmer(int l, int r, int layer) {
int h = (r - l + 1) / 2;
int gap = h;
while (gap > 0) {
int st = h;
bitset<512> chk;
do {
int a =
l + st - gap < 0 ? l + st - gap + (r - l + 1) : l + st - gap;
int b = l + st < 0 ? l + st + r - l + 1 : l + st;
if (chk[a] || chk[b]) {
st++;
if (st == r - l + 1)
st = 0;
continue;
}
net[layer].push_back(minmax(a, b));
// cout << "recmer " << layer << ": " << a << " " << b << endl;
chk[a] = chk[b] = true;
st++;
if (st == r - l + 1)
st = 0;
} while (st != h);
gap /= 2;
layer++;
}
return layer;
}
int recnet(int l, int r, int layer) {
if (l + 1 == r) {
net[layer].push_back({l, r});
// cout << "elem " << layer << ": " << l << " " << r << endl;
return layer + 1;
}
int h = (r - l + 1) / 2;
layer = max(recnet(l, l + h - 1, layer), recnet(l + h, r, layer));
return recmer(l, r, layer);
}
vector<int> ptrs;
void solve(int N, int V) {
net.resize(V);
int target = 2 << (31 - __builtin_clz(N - 1));
recnet(0, target - 1, 0);
ptrs.resize(N);
iota(ptrs.begin(), ptrs.end(), 1);
for (int layer = 0; layer < net.size(); layer++) {
vector<pair<int, int>> sched;
for (auto p : net[layer]) {
if (p.first < N && p.second < N) {
schedule(ptrs[p.first], ptrs[p.second]);
sched.push_back(p);
}
}
if (sched.empty())
continue;
vector<int> v = visit();
for (int i = 0; i < v.size(); i++) {
if (v[i] == 0)
swap(ptrs[sched[i].first], ptrs[sched[i].second]);
}
}
answer(ptrs);
}
Compilation message
swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:60:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int layer = 0; layer < net.size(); layer++) {
| ~~~~~~^~~~~~~~~~~~
swaps.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
