Bottom-Tier Reversals

Created by LXC on Mon Jun 5 00:02:16 2023

https://codeforces.com/problemset/problem/1558/C

ranting: 2000

tag: constructive algorithms, greedy

problem

有一个长度为n的排列，n为奇数。现在每次只能将一个奇数前缀反转前缀。问能否在5n/2次反转前缀操作内将排列变为有序。

不能则输出-1

能则输出操作序列。

solution

由于每次只能操纵前缀。所以先从后缀开始构造。

我们需要找到一个原操作，可以在确定上界的步数内将固定数量的后缀排好序。然后将继续解决规模减小的子问题。

这个原操作不出意外应该是五步内排好2个后缀。

假设当前需要排好的两个后缀是p-1和p。它们在排列中的位置分别是s和e。

那么如果s和e的不相邻.我们可以在两步内让它们相邻：先反转前缀e，使得p在第一位，然后反转前缀s-1，使得p在p-1前面且相邻，即e+1=s。

对于e+1 = s，我们只需反转前缀s+1，便可让p-1在p前面且相邻，即s+1=e.

对于s+1 = e，我们只需反转前缀s，便可让p排在第一位，p-1排在第二位。

最后反转前缀p，既可以排好两个位置p-1和p。

这个过程中最多只需要反转5次。

每次给两个位置p-1和p排序前需要知道它们的位置，所需时间复杂度$O(n)$

总时间复杂度$O(n^2)$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == i % 2) {
            cout << "-1\n";
            return;
        }
    }
    vector<int> ans;
    auto se = [&](int x) -> pair<int, int> {
        int s = find(a.begin(), a.end(), x - 1) - a.begin();
        int e = find(a.begin(), a.end(), x) - a.begin();
        return {s + 1, e + 1};
    };
    auto rvs = [&](int x) {
        reverse(a.begin(), a.begin() + x);
        ans.push_back(x);
    };
    int p = n;
    se(p);
    while (p > 1) {
        auto [s, e] = se(p);
        // cout << s << " " << e << '\n';
        if (s == p - 1 && e == p) {
            p -= 2;
        } else if (s == 2 && e == 1) {
            rvs(p);
        } else if (s + 1 == e) {
            rvs(e);
        } else if (e + 1 == s) {
            rvs(s + 1);
        } else if (e == 1) {
            rvs(s - 1);
        } else {
            rvs(e);
        }
    }
    cout << ans.size() << "\n";
    for (int i : ans) {
        cout << i << ' ';
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}