QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #99737 | #6352. SPPPSPSS. | whatever# | WA | 1ms | 3512kb | C++14 | 1.6kb | 2023-04-23 16:28:14 | 2023-04-23 16:28:15 |
Judging History
answer
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
const int N=1000005;
int n, p[N], ans[N];
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; ++i) scanf("%d", p+i);
int mid=n/2+((n&1)&&(p[n/2+1]<=n/2+1)), ct=0;
for(int i=1; i<=mid; ++i) ct+=(p[i]>mid);
int l=n/2+1, r=l-1;
while(r<n&&p[r+1]==r+1) ++r;
while(l>1&&p[l-1]==l-1) --l;
// printf("%d %d\n", l, r);
if(n%2==0&&(l<=n/2||r>=n/2+1)&&!ct)
{
ans[l-1]=1;
int t=n-r;
if(t) ans[t+(t==l-1)]=2;
goto out;
}
if(n%2==1&&r>=n/2+1&&!ct)
{
ans[l-1]=1;
int t=n-r;
// printf("t %d\n", t);
if(t) ans[t+(t==l-1)]=2;
goto out;
}
{
ans[mid]=1;
ans[(n&1)?n-mid:mid+1]=2;
for(int i=1; i<=n; ++i) if(ans[i])
{
if(ans[i]==2)
{
std::sort(p+n-i+1, p+n+1);
}
else
{
std::sort(p+1, p+i+1);
}
}
l=ct, r=ct;
int i=mid+1;
for(; l>0&&r>0; ++i)
{
if((i-mid)&1) l-=i-(n-(mid+l-r)), ans[i]=2;
else r-=i-(mid+l-r), ans[i]=1;
}
int rt=i;
if(l>0)
{
for(int i=1; i<=l; ++i) if(p[i+mid-ct]!=mid+i)
{
ans[rt]=2;
break;
}
}
if(r>0)
{
for(int i=1; i<=r; ++i) if(p[mid+ct+1-i]!=mid+1-i)
{
ans[rt]=1;
break;
}
}
}
out:;
int t=n;
while(!ans[t]) --t;
for(int i=1; i<=t; ++i) putchar(ans[i]==2?'S':'P');
puts(".");
// for(int i=1; i<=t; ++i)
// {
// if(ans[i]==2)
// {
// std::sort(p+n-i+1, p+n+1);
// }
// else
// {
// std::sort(p+1, p+i+1);
// }
// for(int i=1; i<=n; ++i) printf("%d ", p[i]);
// puts("");
// }
// for(int i=1; i<=n; ++i) printf("%d ", p[i]);
// puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3488kb
input:
3 1 2 3
output:
.
result:
ok OK 0 operations
Test #2:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
2 2 1
output:
PS.
result:
ok OK 2 operations
Test #3:
score: 0
Accepted
time: 1ms
memory: 3376kb
input:
9 3 2 4 1 5 6 7 9 8
output:
PSPP.
result:
ok OK 4 operations
Test #4:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
10 2 9 5 7 10 6 3 1 8 4
output:
PPPPPSPS.
result:
ok OK 8 operations
Test #5:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
13 9 8 5 4 3 2 1 13 12 11 10 7 6
output:
PPPPPSPS.
result:
ok OK 8 operations
Test #6:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
20 17 6 15 14 4 10 18 7 13 8 2 12 1 19 20 3 11 16 5 9
output:
PPPPPPPPPPSPSP.
result:
ok OK 14 operations
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3440kb
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:
PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPSPSPSPSP.
result:
wrong answer Jury (57) found answer better than participant (58)