#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
#define cerr if(0) cout
vector<int> a;
vector<pair<int, int>> visits;
vector<int> idx;
vector<int> whereis;
int n;
int calls = 0;
void interact(int i, int j) {
if(i >= n || j >= n) return;
schedule(idx[i]+1, idx[j]+1);
visits.push_back({idx[i], idx[j]});
calls++;
}
void visitFix() {
vector<int> a = visit();
for(int i = 0; i < calls; i++) {
if(a[i] == 0) {
swap(idx[whereis[visits[i].first]], idx[whereis[visits[i].second]]);
swap(whereis[visits[i].first], whereis[visits[i].second]);
}
}
calls = 0;
visits = vector<pair<int, int>>();
cerr << "\n\n";
for(auto &i : idx) cerr << i << ' ';
cerr << "\n\n";
}
int lg2(int n) {
int res = 0;
while(n != 1) {n>>=1; res++;}
return res;
}
void fix(int sz) {
for(int i = 1; i < sz; i <<= 1) { // block size
// across
for(int j = 0; j*i*2 < n; j += 1) {
for(int k = 0; k < i && k + j*i*2 < n; k++) {
interact(j*i*2 + i - k - 1, k + j*i*2 + i);
}
}
visitFix();
if(i != 1) for(int j = i/2; j > 0; j >>= 1) {
for(int k = 0; k*j*2 < n; k++) {
for(int l = 0; l < j && l + k*j*2 < n; l++) {
interact(k*j*2 + l, k*j*2 + l + j);
}
}
visitFix();
}
}
}
void solve(int N, int v) {
n = N;
int betN = 1<<lg2(n);
if(betN < n) betN *= 2;
for(int i = 0; i < n; i++) idx.push_back(i);
for(int i = 0; i < n; i++) whereis.push_back(i);
a = vector<int>(n);
fix(betN);
for(int i = 0; i < n; i++) a[i] = idx[i]+1;
answer(a);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |