//
// --- 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;
int ans[504];
struct Data{
vector<int> id, mid;
int state;
int nxt[4];
Data(){}
};
Data tr[10004];
int trn;
void solve(int n, int v) {
++trn;
for(int i = 1; i <= n; ++i){
tr[1].id.push_back(i);
}
int m = n;
while(__builtin_popcount(m) != 1){
++m;
tr[1].id.push_back(m);
}
while(tr[1].state != 3){
vector<int> ask;
for(int i = trn; i >= 1; --i){
int lsz = (int)tr[i].id.size() / 2;
int rsz = ((int)tr[i].id.size() + 1) / 2;
if(tr[i].state == 3) continue;
if(lsz + rsz <= 1){
if((int)tr[i].id.size()){
// cout << "SET " << tr[i].id[0] << ' ' << 0 << endl;
ans[tr[i].id[0]] = 0;
}
tr[i].state = 3;
continue;
}
if(tr[i].state == 2){
if(tr[tr[i].nxt[3]].state == 3){
for(auto&j:tr[tr[i].nxt[3]].id){
// cout << "ANSADD " << i << ' ' << j << ' ' << lsz / 2 << endl;
ans[j] += lsz / 2;
}
sort(tr[i].id.begin(), tr[i].id.end(), [&](int&x, int&y){return ans[x] < ans[y];});
// if(tr[i].id == vector<int>{7, 5}){
// cout << "WEF " << ans[5] << ' ' << ans[7] << endl;
// }
// cout << "RES\n";
// for(auto&j:tr[i].id){
// cout << j << ' ';
// }
// cout << endl;
tr[i].state = 3;
}
}
else if(tr[i].state == 1){
if(tr[tr[i].nxt[1]].state == 3 && tr[tr[i].nxt[2]].state == 3){
for(int j = 0; j < lsz; ++j){
if(j < lsz / 2){
// cout << "ANS " << i << ' ' << tr[tr[i].nxt[1]].id[j] << ' ' << j << endl;
ans[tr[tr[i].nxt[1]].id[j]] = j;
}
else{
tr[i].mid.push_back(tr[tr[i].nxt[1]].id[j]);
}
}
for(int j = 0; j < rsz; ++j){
if(j + (rsz + 1) / 2 < rsz){
tr[i].mid.push_back(tr[tr[i].nxt[2]].id[j]);
}
else{
// cout << "ANS " << i << ' ' << tr[tr[i].nxt[2]].id[j] << ' ' << lsz + j << endl;
ans[tr[tr[i].nxt[2]].id[j]] = lsz + j;
}
}
tr[++trn].id = tr[i].mid;
tr[i].nxt[3] = trn;
tr[i].state = 2;
}
}
else if(tr[i].state == 0){
ask.push_back(i);
}
}
if(!(int)ask.size()) continue;
for(auto&i:ask){
int lsz = (int)tr[i].id.size() / 2;
for(int j = 0; j < lsz; ++j){
if(tr[i].id[j] > n || tr[i].id[j + lsz] > n) continue;
schedule(tr[i].id[j], tr[i].id[j + lsz]);
}
}
auto rv = visit();
int rp = 0;
for(auto&i:ask){
int lsz = (int)tr[i].id.size() / 2;
for(int j = 0; j < lsz; ++j){
if(tr[i].id[j] > n || tr[i].id[j + lsz] > n){
if(tr[i].id[j] < tr[i].id[j + lsz]){
swap(tr[i].id[j], tr[i].id[j + lsz]);
}
}
else{
if(!rv[rp]){
swap(tr[i].id[j], tr[i].id[j + lsz]);
}
++rp;
}
}
}
for(auto&i:ask){
int lsz = (int)tr[i].id.size() / 2;
tr[i].state = 1;
++trn;
tr[i].nxt[1] = trn;
for(int j = 0; j < lsz; ++j) tr[trn].id.push_back(tr[i].id[j]);
++trn;
tr[i].nxt[2] = trn;
for(int j = lsz; j < (int)tr[i].id.size(); ++j){
tr[trn].id.push_back(tr[i].id[j]);
}
}
}
vector<int> rv(n);
for(int i = 1; i <= n; ++i){
// cout << ans[i] << endl;
rv[ans[i] - (m - n)] = i;
}
answer(rv);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
976 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
