QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #199678 | #6352. SPPPSPSS. | ucup-team870# | TL | 7ms | 5900kb | C++14 | 2.7kb | 2023-10-04 13:41:56 | 2023-10-04 13:41:57 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N = 1000010;
int n, cnt, p[N], vis[N], ans;
priority_queue <int> ss;
priority_queue <int, vector<int>, greater<int> > tt;
bool check() {
int f1 = ss.size() == 0 || ss.top() == ss.size();
int f2 = tt.size() == 0 || tt.top() == n - int(tt.size()) + 1;
if (cnt == 0 && f1 && f2) return true;
return false;
}
int main() {
scanf("%d", &n);
rep (i, 1, n) {
scanf("%d", &p[i]);
if (p[i] != i) vis[i] = 1, cnt++;
}
ans = n;
int flag = 0;
int l = 0, r = n+1;
rep (i, 1, n) {
if (check()) {
ans = min(ans, i-1);
break;
}
if (i & 1) {
while (l < i) {
l++;
if (l < r) cnt -= vis[l], ss.push(p[l]);
else {
ss.push(tt.top());
tt.pop();
r++;
}
}
} else {
while (r > n-i+1) {
r--;
if (l < r) cnt -= vis[r], tt.push(p[r]);
else {
tt.push(ss.top());
ss.pop();
l--;
}
}
}
}
while (!ss.empty()) ss.pop();
while (!tt.empty()) tt.pop();
// cout <<"#";
rep (i, 1, n) cnt += vis[i];
l = 0, r = n+1;
rep (i, 1, n) {
// cout<<i;
if (check()) {
if (i-1 < ans) {
flag = 1;
ans = i-1;
break;
}
}
if (!(i & 1)) {
while (l < i) {
l++;
if (l < r) cnt -= vis[l], ss.push(p[l]);
else {
ss.push(tt.top());
tt.pop();
r++;
}
}
} else {
while (r > n-i+1) {
r--;
if (l < r) cnt -= vis[r], tt.push(p[r]);
else {
tt.push(ss.top());
ss.pop();
l--;
}
}
}
}
if (flag == 0) {
rep (i, 1, ans) {
if (i & 1) cout << 'P';
else cout << 'S';
}
} else {
rep (i, 1, ans) {
if (i & 1) cout << 'S';
else cout << 'P';
}
}
cout <<'.';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5880kb
input:
3 1 2 3
output:
.
result:
ok OK 0 operations
Test #2:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
2 2 1
output:
PS.
result:
ok OK 2 operations
Test #3:
score: 0
Accepted
time: 1ms
memory: 5696kb
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: 5832kb
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: 5836kb
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: 1ms
memory: 5832kb
input:
20 17 6 15 14 4 10 18 7 13 8 2 12 1 19 20 3 11 16 5 9
output:
PSPSPSPSPSPSPS.
result:
ok OK 14 operations
Test #7:
score: 0
Accepted
time: 0ms
memory: 5696kb
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:
PSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSP.
result:
ok OK 57 operations
Test #8:
score: 0
Accepted
time: 7ms
memory: 5900kb
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:
PSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPSPS...
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...