답안 #158926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
158926 2019-10-19T15:03:07 Z bruce_test Ranklist Sorting (BOI07_sorting) C++11
30 / 100
15 ms 8312 KB
#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

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;
         ~~~~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 6 ms 4316 KB Output is correct
3 Incorrect 6 ms 4344 KB not sorted
4 Incorrect 6 ms 4472 KB not sorted
5 Incorrect 6 ms 4728 KB not sorted
6 Incorrect 8 ms 5112 KB not sorted
7 Incorrect 9 ms 6264 KB not sorted
8 Incorrect 12 ms 7416 KB not sorted
9 Correct 14 ms 8312 KB Output is correct
10 Incorrect 15 ms 8184 KB not sorted