oj.uz

Submission #718850

# Submission time Handle Problem Language Result Execution time Memory
718850 2023-04-05T01:20:34 Z nicksms Ranklist Sorting (BOI07_sorting) C++17
100 / 100
 7 ms 8148 KB 
/**
 *      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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 6 ms 6612 KB Output is correct
9 Correct 7 ms 8148 KB Output is correct
10 Correct 7 ms 8148 KB Output is correct