QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#286505 | #7960. 排序大师 | ucup-team022 | TL | 0ms | 3436kb | C++17 | 4.7kb | 2023-12-17 22:59:06 | 2023-12-17 22:59:06 |
Judging History
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();
}
详细
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 ...