| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 198878 | imaxblue | Ranklist Sorting (BOI07_sorting) | C++17 | 41 ms | 13304 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define vi vector<int>
#define vpii vector<pii>
#define vp3i vector<p3i>
#define vpll vector<pll>
#define vp3l vector<p3l>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() ((rand() << 14)+rand())
#define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0)
char _;
#define pi 3.14159265358979323846
int n, a[1005], dp[1005][1005], p[1005], psa[1005][1005], psa2[1004][1005];
bool nxt[1005][1005], rem[1005];
vector<pii> v;
int solve(int N, int L){
if (N==n) return 0;
if (dp[N][L]!=0x3f3f3f3f) return dp[N][L];
int P=p[N];
dp[N][L]=min(dp[N][L], solve(N+1, L)+P+1+(n-N)-psa[p[N]][N]+1);
if (!(P>=L)){
int t=solve(N+1, P)+psa2[p[N]][N]-1;
dp[N][L]=min(dp[N][L], t);
if (t==dp[N][L]) nxt[N][L]=1;
}
return dp[N][L];
}
vector<int> v2;
vector<pii> res, ed;
void out(int N, int L){
if (N==n) return;
if (nxt[N][L]==0){
if (p[N]>=L){
//cout << "*";
ed.pb(mp(p[N], N));
} else {
//cout << N << ' '<< L << endl;
//fox(l, v2.size()) cout << v2[l] << ' '; cout << endl;
fox(l, v2.size()){
if (v2[l]==N){
v2.erase(v2.begin()+l);
fox(l2, v2.size()+1){
if (l2==v2.size() || v2[l2]<N){
res.pb(mp(l+1, l2+1));
v2.insert(v2.begin()+l2, N);
break;
}
}
break;
}
}
}
out(N+1, L);
} else {
out(N+1, p[N]);
}
}
vector<int> v3;
void verify(){
fox(l, res.size()){
int t=v3[res[l].x-1];
v3.erase(v3.begin()+res[l].x-1);
v3.insert(v3.begin()+res[l].y-1, t);
}
fox(l, int(v3.size())-1){
if (v3[l]<v3[l+1]) exit(1);
}
}
int32_t run(){
flood(dp);
v3.clear(); v2.clear(); v.clear();
drain(psa); drain(psa2);
res.clear(); ed.clear();
drain(rem); drain(nxt);
fox(l, n){
v3.pb(a[l]);
v.pb(mp(a[l], l));
}
sort(v.begin(), v.end());
fox(l, n){
a[v[l].y]=l;
p[l]=v[l].y;
}
fox(l, n){
v2.pb(a[l]);
psa[l][a[l]]++;
psa2[l][a[l]]++;
}
foxr(l, n){
foxr(l2, n){
psa[l][l2]+=psa[l+1][l2]+psa[l][l2+1]-psa[l+1][l2+1];
}
}
fox(l, n){
fox(l2, n){
if (l>0) psa2[l][l2]+=psa2[l-1][l2];
if (l2>0) psa2[l][l2]+=psa2[l][l2-1];
if (l>0 && l2>0) psa2[l][l2]-=psa2[l-1][l2-1];
//cout<< psa2[l][l2] << ' ';
}
//cout << endl;
}
int x=solve(0, n);
//cout << x << endl;
out(0, n);
//fox(l, v2.size()) cout << v2[l] << ' ';
sort(ed.begin(), ed.end());
foxr(l, v2.size()){
p[v2[l]]=l;
}
fox(l, ed.size()){
//cout << ed[l].x << ' ' << ed[l].y << endl;
rem[ed[l].y]=1;
}
foxr(l, v2.size()){
if (rem[v2[l]]) v2.erase(v2.begin()+l);
}
//fox(l, v2.size()) cout << v2[l] << ' '; cout << endl;
fox(l, ed.size()){
int N=ed[l].y;
for(int l2=0; l2<v2.size(); ++l2){
if ((l2==0 || v2[l2-1]>N) && N>v2[l2]){
v2.insert(v2.begin()+l2, N);
res.pb(mp(p[N]+1, l2+1));
break;
}
}
}
cout << res.size() << endl;
fox(l, res.size()) cout << res[l].x << ' ' << res[l].y << endl;
verify();
return 0;
}
void test(){
int b[10];
fox(l, n) b[l]=l;
do {
fox(l, n){
cout << b[l] << ' ';
a[l]=b[l];
} cout << endl;
run();
} while(next_permutation(b, b+n));
}
int32_t main(){
cin >> n;
//test
//test();
fox(l, n){
scanf("%i", &a[l]);
}
run();
return 0;
}
//10
//0 1 2 3 4 6 8 7 5 9
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||