oj.uz

답안 #137490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137490 2019-07-28T04:48:19 Z gs14004 Ranklist Sorting (BOI07_sorting) C++17
100 / 100
 20 ms 8184 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, a[1005], aux[1005], pos[1005];
int dp[1005][1005], nxt[1005][1005];
int chk[1005];

int main(){
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> aux[i];
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(aux[j] >= aux[i]) a[i]++;
		}
	}
	a[n+1] = n+1;
	n++;
	for(int i=1; i<=n; i++) pos[a[i]] = i;
	memset(dp, 0x3f, sizeof(dp));
	dp[n][n] = 0;
	for(int i=n-1; i; i--){
		int p1 = 1, p2 = 1;
		for(int j=1; j<i; j++){
			if(pos[j] < pos[i]) p1++;
		}
		for(int j=1; j<=n; j++){
			dp[i][j] = dp[i+1][j] + p1 + p2;
			nxt[i][j] = j;
			if(a[j] < i) p2++;
		}
		int cost = 0;
		for(int j=pos[i]+1; j<=n; j++){
			if(dp[i][pos[i]] > dp[i+1][j] + cost){
				dp[i][pos[i]] = dp[i+1][j] + cost;
				nxt[i][pos[i]] = j;
			}
			if(a[j] < i) cost += i - a[j];
		}
	}
	int tmp = 1e9, tra = 0;
	for(int i=1; i<=n; i++){
		if(tmp > dp[1][i]){
			tmp = dp[1][i];
			tra = i;
		}
	}
	for(int i=1; i<=n; i++){
		if(nxt[i][tra] != tra){
			chk[i] = 1;
		}
		tra = nxt[i][tra];
	}
	vector<pi> dap;
	for(int i=n-1; i; i--){
		if(!chk[i]){
			int st = -1, ed = -1;
			for(int j=1; j<=n; j++){
				if(a[j] == i) st = j;
				if(a[j] == i+1) ed = j;
			}
			if(st < ed){
				ed--;
				dap.push_back({st, ed});
				for(int j=st; j<ed; j++){
					a[j] = a[j+1];
				}
				a[ed] = i;
			}
			else{
				dap.push_back({st, ed});
				for(int j=st; j>ed; j--){
					a[j] = a[j-1];
				}
				a[ed] = i;
			}
		}
	}
	cout << dap.size() << endl;
	for(auto &i : dap) cout << i.first << " " << i.second << endl;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 6 ms 4344 KB Output is correct
3 Correct 5 ms 4344 KB Output is correct
4 Correct 6 ms 4472 KB Output is correct
5 Correct 6 ms 4684 KB Output is correct
6 Correct 7 ms 5116 KB Output is correct
7 Correct 10 ms 6264 KB Output is correct
8 Correct 16 ms 7544 KB Output is correct
9 Correct 17 ms 8184 KB Output is correct
10 Correct 20 ms 8184 KB Output is correct