This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "swaps.h"
#include <bits/stdc++.h>
#define ar array
using namespace std;
//
// --- 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.
//
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<ar<int, 2>> lvls[5000];
int solve_range(int l, int r) {
int mid = l + (r-l+1)/2;
int lvl = 0;
if (l != mid-1) lvl = max(lvl, solve_range(l, mid-1));
if (r != mid) lvl = max(lvl, solve_range(mid, r));
cerr << l << ' ' << r << '\n';
int gap = r-l+1;
do {
gap = (gap+1)/2;
cerr << gap << '\n';
set<ar<int, 2>> need;
for (int i = l, j = l+gap; j <= r; ++i, ++j)
need.insert({i, j});
while (need.size()) {
set<int> taken;
for (auto it = need.begin(); it != need.end();) {
auto [i, j] = *it;
if (taken.count(i) || taken.count(j)) {
++it;
continue;
}
else {
lvls[lvl].push_back({i, j});
taken.insert(i);
taken.insert(j);
need.erase(it++);
}
}
++lvl;
}
} while (gap > 1);
return lvl+1;
}
void solve(int n, int v) {
vector<int> a(n);
iota(a.begin(), a.end(), 0);
int v_needed = solve_range(0, n-1);
cerr << "used, allowed: "<< v_needed << ' ' << v << '\n';
for (int lvl = 0; lvl < v_needed; ++lvl) {
//*
for (auto [i, j] : lvls[lvl])
cerr << '(' << i << ' ' << j << ") ";
cerr << '\n'; // */
//*
vector<ar<int, 2>> scheduled;
for (auto [i, j] : lvls[lvl]) {
scheduled.push_back({i, j});
schedule(a[i]+1, a[j]+1);
}
auto res = visit();
for (int I = 0; I < (int)scheduled.size(); ++I) {
auto [i, j] = scheduled[I];
if (!res[I]) swap(a[i], a[j]);
}
}
vector<int> inv(n);
for (int i = 0; i < n; ++i)
inv[a[i]] = i+1;
answer(inv);
}
# | 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... |