QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #99767 | #6352. SPPPSPSS. | whatever# | WA | 3ms | 9052kb | C++17 | 2.6kb | 2023-04-23 17:48:04 | 2023-04-23 17:48:07 |
Judging History
answer
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
using std::priority_queue;
const int N=1000005;
int n, p[N], rp[2][N], ra[2], ans[N];
priority_queue<int> ql;
priority_queue<int, std::vector<int>, std::greater<int> > qr;
int solve(int *p, int i)
{
while(!ql.empty()&&ql.top()>ql.size())
{
++i;
// printf("sz %d %d %d %d %d\n", i, ql.size(), qr.size(), ql.top(), qr.top());
if(ql.size()==i-1&&ql.top()==ql.size()+1)
{
p[i]=1;
return i;
}
if(qr.size()==i-1&&qr.top()==n-(int)qr.size())
{
p[i]=2;
return i;
}
if(ql.size()==i-1)
{
p[i]=2;
while(qr.size()<i) qr.push(ql.top()), ql.pop();
}
if(qr.size()==i-1)
{
p[i]=1;
while(ql.size()<i) ql.push(qr.top()), qr.pop();
}
}
// printf("sz %d %d %d %d %d\n", i, ql.size(), qr.size(), ql.top(), qr.top());
return i;
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; ++i) scanf("%d", p+i);
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;
// if(l<=n/2) std::sort(p+1, p+l);
// if(r>=n/2+1) std::sort(p+r+1, p+n+1);
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);
// 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;
}
{
for(int ct:{0, 1})
{
int t=ct;
while(!ql.empty()) ql.pop();
while(!qr.empty()) qr.pop();
int l=1, r=n, i=0;
while(1)
{
++i;
// printf("%d %d\n",l ,r);
rp[ct][i]=t+1;
if(!t)
{
while(r>=std::max(l, n-i+1)) qr.push(p[r]), --r;
if(r==l-1)
{
while(qr.size()<i) qr.push(ql.top()), ql.pop();
break;
}
}
else
{
while(l<=std::min(r, i)) ql.push(p[l]), ++l;
if(r==l-1)
{
while(ql.size()<i) ql.push(qr.top()), qr.pop();
break;
}
}
t^=1;
}
ra[ct]=solve(rp[ct], i);
}
if(ra[0]<ra[1]) std::copy(rp[0], rp[0]+n+1, ans);
else std::copy(rp[1], rp[1]+n+1, ans);
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 4884kb
input:
3 1 2 3
output:
.
result:
ok OK 0 operations
Test #2:
score: 0
Accepted
time: 0ms
memory: 4940kb
input:
2 2 1
output:
SP.
result:
ok OK 2 operations
Test #3:
score: 0
Accepted
time: 2ms
memory: 4956kb
input:
9 3 2 4 1 5 6 7 9 8
output:
PSPP.
result:
ok OK 4 operations
Test #4:
score: 0
Accepted
time: 3ms
memory: 9052kb
input:
10 2 9 5 7 10 6 3 1 8 4
output:
SPSPSPPS.
result:
ok OK 8 operations
Test #5:
score: -100
Wrong Answer
time: 3ms
memory: 9024kb
input:
13 9 8 5 4 3 2 1 13 12 11 10 7 6
output:
SPSPSPSS.
result:
wrong answer the permutation is not sorted