Submission #158926

#	Time	Username	Problem	Language	Result	Execution time	Memory
158926		bruce_test	Ranklist Sorting (BOI07_sorting)	C++11	30 / 100	15 ms	8312 KiB

sorting

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef pair<int, int> pi;
const int MM = 1005, INF=0x3f3f3f3f;
int N, p[MM], cnt[MM][MM], ans=INF, dp[MM][MM], st, dep[MM], tot, bit[MM]; pi a[MM];
bool cmp(pi x, pi y){ return x.s < y.s;}
void upd(int pos, int val){
    for(int i=pos; i<=N; i+=i&-i)
        bit[i] += val;
}
int qry(int pos) {
    int ret = 0;
    for(int i=pos; i; i-=i&-i) ret += bit[i];
    return ret;
}
void recur(int cur, int best) {
    if(cur == N+1) return;
    if(p[cur] == best) recur(cur+1, dep[cur]);
    else { a[tot++] = {p[cur], cur}; recur(cur+1, best); }
}
int main(){
    //freopen("test.txt", "r", stdin);
    scanf("%d", &N);
    for(int i=1; i<=N; i++){
        scanf("%d", &a[i].f); a[i].s = i;
    }
    sort(a+1, a+N+1, greater<pi>());
    for(int i=1; i<=N; i++) {
        p[i] = a[i].s; a[i].f = i;
    }
    sort(a+1, a+N+1, cmp);
    for(int i=1; i<=N; i++)
        cnt[a[i].f+1][i+1]++;
    for(int i=1; i<=N+1; i++)
        for(int j=1; j<=N+1; j++)
            cnt[i][j] += cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1];
    memset(dp, 0x3f, sizeof(dp));
    a[N+1].f = N+1; dp[N+1][N+1] = 0;
    for(int i=N; i>=1; i--){
        for(int j=1; j<=N+1; j++)
            if(dp[i+1][j] != INF) dp[i][j] = dp[i+1][j] + cnt[i][p[i]] + cnt[i][j] + 2;
        for(int j=p[i]+1, val=0; j<=N+1; j++){
            if(dp[i][p[i]] >= dp[i+1][j] + val){
                dp[i][p[i]]= dp[i+1][j]+val;
                dep[i] = j;
            }
            if(a[j].f < i) val = val + i - a[j].f;
        }
    }
//    for(int i=1; i<=N+1; i++){
//        for(int j=1; j<=N+1; j++){
//            if(dp[i][j] == INF) cout << "INF\t";
//            else cout << dp[i][j] << "\t";
//        }
//        cout << endl;
//    }
    for(int i=1; i<=N; i++){
        if(dp[1][i] <= ans) ans = dp[1][i], st = i;
        upd(i, 1);
    }
    recur(1, st);
    printf("%d\n", tot);
    for(int i=tot-1; i>=0; i--){
        printf("%d %d\n", qry(a[i].first), a[i].second);
        upd(a[i].first, -1);
    }
}

Compilation message (stderr)

sorting.cpp: In function 'int main()':
sorting.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
sorting.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i].f); a[i].s = i;
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 30 / 100