QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#286505#7960. 排序大师ucup-team022TL 0ms3436kbC++174.7kb2023-12-17 22:59:062023-12-17 22:59:06

Judging History

你现在查看的是最新测评结果

  • [2023-12-17 22:59:06]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3436kb
  • [2023-12-17 22:59:06]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
const int N=2005;
using namespace std;

int n;
int a[N],b[N];
int ia[N];
int calc(){
    int res = 0;
    for(int i=1;i<n;i++)if(a[i]!=a[i+1]-1)res++;
    return res;
}
vector<vector<int>> res;
void swap(int i,int j,int k,int l){
    int cnt = 0;
    for(int o=1;o<i;o++)b[++cnt]=a[o];
    for(int o=k;o<=l;o++)b[++cnt]=a[o];
    for(int o=j+1;o<=k-1;o++)b[++cnt]=a[o];
    for(int o=i;o<=j;o++)b[++cnt]=a[o];
    for(int o=l+1;o<=n;o++)b[++cnt]=a[o];
    assert(cnt==n);
    for(int i=1;i<=n;i++)a[i]=b[i];
    for(int i=1;i<=n;i++)ia[a[i]]=i;
    res.push_back({i,j,k,l});
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)ia[a[i]]=i;ia[n+1]=n+1; 
    int ans = 0;
    while(calc()){
        int m = 0;
        int I=-1, J=-1, K=-1, L=-1;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q1, q2;
        q1.push({100000,-1});
        q2.push({100000,-1}); 
        for(int i=1;i<=n;i++){
            if(a[i]!=a[i-1]+1){//asi
                int x = n+1, y = n+1;
                if( a[i]!=1 )
                    x = ia[a[i]-1]+1;
                if( i != 1 && a[i-1] != n )
                    y = ia[a[i-1]+1];
                if( x == y )	
                    q2.push( {x, i} );
                else {
                    q1.push( {x, i} ); 
                    q1.push( {y, i} ); 
                }
            }
            if(a[i]!=a[i+1]-1){//asj
                while(q1.top().first < i+2)q1.pop();
                while(q2.top().first < i+2)q2.pop();
                int x = -1, y = -1;
                if( a[i]!=n )
                    x = ia[a[i]+1]-1;
                if( i != n && a[i+1] != 1 ) 
                    y = ia[a[i+1]-1];
                if( x == y ){
                    if( x == -1 )continue;
                    if( q2.top().first <= x ) {
                        if( m < 4 ){
                            m = 4;
                            I = q2.top().second;
                            J = i;
                            K = q2.top().first;
                            L = x;
                        }
                    }
                    if( q1.top().first <= x ) {
                        if( m < 3 ){
                            m = 3;
                            I = q1.top().second;
                            J = i;
                            K = q1.top().first;
                            L = x;
                        }
                    }
                }else{
                    if( q2.top().first <= x ) {
                        if( m < 3 ){
                            m = 3;
                            I = q2.top().second;
                            J = i;
                            K = q2.top().first;
                            L = x;
                        }
                    }
                    if( q2.top().first <= y ) {
                        if( m < 3 ){
                            m = 3;
                            I = q2.top().second;
                            J = i;
                            K = q2.top().first;
                            L = y;
                        }
                    }
                    if( q1.top().first <= x ) {
                        if( m < 2 ){
                            m = 2;
                            I = q1.top().second;
                            J = i;
                            K = q1.top().first;
                            L = x;
                        }
                    }
                    if( q1.top().first <= y ) {
                        if( m < 2 ){
                            m = 2;
                            I = q1.top().second;
                            J = i;
                            K = q1.top().first;
                            L = y;
                        }
                    }
                }
            }
        }
        for(int i=1;i<n;i++){
            int x=a[i],y=a[i+1];
            int l=ia[y-1]+1,r=ia[x+1]-1;
            if(l<=i&&i+1<=r){
                int res = 0;
                if(l!=1)res++;
                if(r!=n)res++;
                if(a[r]+1==a[l])res++;
                if( m < res ){
                    m = res;
                    I = l;
                    J = i;
                    K = i+1;
                    L = r;
                }
            }
        }
        swap(I,J,K,L);
        ans++;
    }
    cout << ans << endl;
    for(auto x:res){
        for(auto y:x)
            cout << y << ' ';
        cout << endl;
    }
}

main(){
    ios::sync_with_stdio(0);
    int _T=1;//cin>>_T;
    while(_T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3436kb

input:

1
1

output:

0

result:

ok orz U R the sorting master!

Test #2:

score: -100
Time Limit Exceeded

input:

1970
1452 1799 174 371 132 637 23 1510 1819 1794 1665 450 1183 564 1305 548 554 1310 701 1454 1843 1498 1040 1678 77 614 1928 1761 1718 1637 1853 1026 1804 1062 805 864 1859 586 663 346 335 681 152 1768 1639 1713 856 1401 1833 1350 1842 558 241 1829 802 581 1958 845 722 239 1793 1118 1251 1892 1949 ...

output:

981
1 1 433 1724 
1 1 1263 1488 
1 1 1056 1260 
2 2 253 377 
2 2 1178 1275 
3 3 504 916 
3 3 315 933 
4 4 1006 1083 
6 6 708 780 
5 6 1117 1570 
5 5 127 1437 
6 6 58 1731 
7 7 301 370 
6 6 1034 1552 
7 7 575 1951 
1 7 1290 1646 
3 3 406 1693 
2 2 489 1745 
3 3 781 1856 
2 3 478 1819 
4 5 133 623 
4 ...

result: