QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #99979 | #6352. SPPPSPSS. | Wolam | TL | 3ms | 3508kb | C++14 | 2.1kb | 2023-04-24 11:33:34 | 2023-04-24 11:33:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
int n,a[100005];
int b[100005];
string ans1,ans2;
void presort(int x,int *a)
{
sort(a+1,a+x+1);
}
void sufsort(int x,int *a)
{
//if(x<=n)cerr<<x<<endl;
sort(a+n-x+1,a+n+1);
}
bool check()
{
for(int i=1;i<=n;i++)
if(b[i]!=i)return 0;
return 1;
}
void solpre()
{
int t=(n+1)/2;
for(int i=1;i<=n;i++)
b[i]=a[i];
presort(t,b);
sufsort(t-1,b);
if(!check())
{
for(int i=1;i<=t;i++)
if((i+t)&1)ans1+='S';
else ans1+='P';
//cerr<<t<<endl;
int i=t+1;
while(!check())
{
if((i+t)&1)sufsort(i,b),ans1+='S';
else presort(i,b),ans1+='P';
//i++;
/* if(i<=n)
{
for(int i=1;i<=n;i++)
cerr<<b[i]<<" ";
cerr<<endl;
}*/
i++;
}
}
else
{
int now=0;
for(int i=t;i>=1;i--)
{
if((i+t)&1)
{
if(a[n-i+1]!=n-i+1||a[n-i+2]!=n-i+2)
{
now=i;
break;
}
}
else if(a[i]!=i||a[i-1]!=i-1)
{
now=i;
break;
}
}
for(int i=1;i<=now;i++)
if((i+t)&1)ans1+='S';
else ans1+='P';
}
}
void solsuf()
{
int t=(n+1)/2;
for(int i=1;i<=n;i++)
b[i]=a[i];
presort(t-1,b);
sufsort(t,b);
if(!check())
{
for(int i=1;i<=t;i++)
if((i+t)&1)ans2+='P';
else ans2+='S';
int i=t+1;
while(!check()&&ans2.size()<ans1.size())
{
if((i+t)&1)presort(i,b),ans2+='P';
else sufsort(i,b),ans2+='S';
i++;
// cerr<<i<<endl;
}
}
else
{
int now=0;
for(int i=t;i>=1;i--)
{
if((i+t)&1)
{
if(a[i]!=i||a[i-1]!=i-1)
{
now=i;
break;
}
}
else if(a[n-i+1]!=n-i+1||a[n-i+2]!=n-i+2)
{
now=i;
break;
}
}
for(int i=1;i<=now;i++)
if((i+t)&1)ans2+='P';
else ans2+='S';
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
a[n+1]=n+1;
solpre();
solsuf();
for(int i=1;i<=n;i++)
if(i&1)sufsort(i,a);
else presort(i,a);
// for(int i=1;i<=n;i++)
// cout<<a[i]<<" ";
if(ans1.size()<=ans2.size())
cout<<ans1;
else cout<<ans2;
cout<<'.';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3340kb
input:
3 1 2 3
output:
.
result:
ok OK 0 operations
Test #2:
score: 0
Accepted
time: 2ms
memory: 3348kb
input:
2 2 1
output:
PS.
result:
ok OK 2 operations
Test #3:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
9 3 2 4 1 5 6 7 9 8
output:
SPSP.
result:
ok OK 4 operations
Test #4:
score: 0
Accepted
time: 1ms
memory: 3384kb
input:
10 2 9 5 7 10 6 3 1 8 4
output:
PSPSPSPS.
result:
ok OK 8 operations
Test #5:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
13 9 8 5 4 3 2 1 13 12 11 10 7 6
output:
PSPSPSPS.
result:
ok OK 8 operations
Test #6:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
20 17 6 15 14 4 10 18 7 13 8 2 12 1 19 20 3 11 16 5 9
output:
SPSPSPSPSPSPSP.
result:
ok OK 14 operations
Test #7:
score: 0
Accepted
time: 2ms
memory: 3508kb
input:
100 98 85 81 18 27 10 68 48 19 2 55 51 61 20 91 54 35 22 83 75 8 5 17 23 21 95 37 15 92 50 78 82 44 39 26 87 52 66 70 74 89 4 59 40 12 88 86 43 14 80 53 46 63 3 36 97 60 58 57 96 11 67 99 41 34 47 71 72 73 79 9 94 6 1 77 25 31 7 45 100 90 32 24 13 76 16 93 38 29 69 42 84 30 28 33 56 49 62 64 65
output:
SPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPS.
result:
ok OK 57 operations
Test #8:
score: 0
Accepted
time: 3ms
memory: 3416kb
input:
1000 668 554 210 852 617 846 561 95 341 893 276 224 287 1000 356 362 897 205 369 654 181 590 339 377 346 557 382 593 55 62 126 899 49 509 977 585 614 232 865 800 790 292 219 957 379 914 946 246 294 403 940 517 768 623 376 624 331 353 887 626 424 449 115 628 569 809 956 942 300 894 61 936 678 779 549...
output:
SPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSP...
result:
ok OK 523 operations
Test #9:
score: -100
Time Limit Exceeded
input:
100000 30619 15529 4854 9258 46894 29948 59533 56945 19473 7608 42291 95532 80537 83105 70434 68130 89221 96367 26768 43837 54765 52814 88446 14950 63224 63479 11957 41446 38702 8466 85556 57724 50097 29014 17961 65178 88627 96815 80115 79096 19625 2979 51033 68224 48649 96250 3406 96433 22584 79610...