Submission #718850

#	Time	Username	Problem	Language	Result	Execution time	Memory
718850		nicksms	Ranklist Sorting (BOI07_sorting)	C++17	100 / 100	7 ms	8148 KiB

sorting

/**
 *      Author:  Nicholas Winschel
 *      Created: 04.04.2023 20:21:56
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
using pi = pair<int,int>;
using vpi = vector<pi>;

int dp[1001][1001],last[1001][1001];

template<class T> void cm(T &a, const T &b) {
    if (b < a) a = b;
}

int main(){
    cin.tie(0)->sync_with_stdio(0); // initialize fast I/O

    int n; cin >> n;
    vpi vals;
    for (int i = 0; i < n; i++) {
        int c; cin >> c; vals.emplace_back(-c,i);
    }
    sort(vals.begin(),vals.end());
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        p[vals[i].second]=i;
    }
    p.push_back(n);
    vals.emplace_back(-1,n);

    for (int i = 0; i < n; i++) dp[n][i]=1e9;
    dp[n][n]=0;

    for (int i = n-1; i >= 0; i--) {
        int v = 1;
        for (int j = 0; j < vals[i].second; j++) if (p[j]<i) v++;
        int v2 = 1;
        for (int h = 0; h <= n; h++) {
            if (p[h] < i) v2++;
            dp[i][h] = dp[i+1][h]+v+v2;
            last[i][h] = h;
        }
        int o = 0;
        for (int k = vals[i].second+1; k <= n; k++) {
            int t = dp[i+1][k]+o;
            if (t < dp[i][vals[i].second]) {
                dp[i][vals[i].second] = t;
                last[i][vals[i].second] = k;
            }
            o += max(0, i-p[k]);
        }
    }
    pi best{1e9, -1};
    for (int i = 0; i <= n; i++) cm(best, {dp[0][i],i});
    assert(best.second>=0);
    bitset<1001> b;
    for (int i = 0; i < n; i++) {
        if (best.second == vals[i].second) b[i] = true;
        best.second = last[i][best.second];
    }
    vpi m;
    for (int i = n-1; i >= 0; i--) {
        if (b[i]) continue;
        int f = find(p.begin(), p.end(), i)-p.begin();
        int t = find(p.begin(), p.end(), i+1)-p.begin();
        m.emplace_back(f+1,t>f?t:t+1);
        p.erase(p.begin()+f);
        p.insert(find(p.begin(),p.end(), i+1),i);
    }

    cout << m.size() << "\n";

    for (auto &&p : m) {
        cout << p.first << " " << p.second << "\n";
    }

    return 0;
}

• Subtask 1: 100 / 100