QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #240666 | #6352. SPPPSPSS. | jzh# | WA | 1ms | 5540kb | C++20 | 4.6kb | 2023-11-05 17:25:53 | 2023-11-05 17:25:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n;
int a[N];
char SP[N];
void fun() {
int m = (n+1)/2;
vector<int> L, R;
string tmpans1, tmpans;
string ans1, ans2;
int mnt = 1e9;
// check P at m
L.clear();
R.clear();
for (int i=1; i<=m; i++) if (a[i] > m) L.push_back(a[i]);
for (int i=m+1; i<=n; i++) if (a[i] < m) R.push_back(a[i]);
sort(L.begin(), L.end());
sort(R.rbegin(), R.rend());
tmpans1 = tmpans = "";
for (int t=m-1, f=0; t>=1; t--, f^=1) {
tmpans1 += "S";
}
for (int t=m, f=0, pl=L.size(), pr=R.size(); t<=n && (pl>0 || pr>0); t++, f^=1) {
if (f == 0) { // P
tmpans+="P";
int d = t-m;
// if (d >= pr) {
// if (t < mnt) {
// mnt = t;
// ans1 = tmpans1;
// ans2 = tmpans;
// }
// }
pr -= d;
}
else { // S
tmpans += "S";
int d = t - (n - m);
// if (d >= pl) {
// if (t < mnt) {
// mnt = t;
// ans1 = tmpans1;
// ans2 = tmpans;
// }
// }
pl -= d;
}
if (pl<=0 && pr<=0) {
if (t < mnt) {
mnt = t;
ans1 = tmpans1;
ans2 = tmpans;
}
}
}
// check S at m
L.clear();
R.clear();
for (int i=1; i<m; i++) if (a[i] > m) L.push_back(a[i]);
for (int i=m; i<=n; i++) if (a[i] < m) R.push_back(a[i]);
sort(L.begin(), L.end());
sort(R.rbegin(), R.rend());
tmpans1 = tmpans = "";
for (int t=m-1, f=0; t>=1; t--, f^=1) {
tmpans1 += "P";
}
for (int t=m, f=0, pl=L.size(), pr=R.size(); t<=n && (pl>0 || pr>0); t++, f^=1) {
if (f == 0) { // S
tmpans+="S";
int d = t-m;
// if (d >= pl) {
// if (t < mnt) {
// mnt = t;
// ans1 = tmpans1;
// ans2 = tmpans;
// }
// break;
// }
pl -= d;
}
else { // P
tmpans += "P";
int d = t-(n-m);
// if (d >= pr) {
// if (t < mnt) {
// mnt = t;
// ans1 = tmpans1;
// ans2 = tmpans;
// }
// break;
// }
pr -= d;
}
if (pl<=0 && pr<=0) {
if (t < mnt) {
mnt = t;
ans1 = tmpans1;
ans2 = tmpans;
}
}
}
cout <<ans1 <<ans2 <<".\n";
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int cntl = 0, cntr = 0;
for (int i = 1; i <= (n / 2); i++) {
cntl += (a[i] > (n + 1) / 2);
}
for (int i = ((n+1) / 2)+1; i <= n; i++) {
cntr += (a[i] < (n + 1) / 2);
}
//assert(cntl == cntr);
if (cntl == 0 && cntr == 0) {
int max_l = 0, max_r = 0;
for (int i = 1; i <= n; i++) {
if (a[i] != i) {
if (a[i] <= (n+1)/2 && i<=(n+1)/2) max_l = max(max_l, a[i]);
if (a[i] >= (n+1)/2 && i>=(n+1)/2) max_r = max(max_r, n - a[i] + 1);
}
}
if (max_l == 0 && max_r == 0) {
cout << ".";
return 0;
}
if (max_l == max_r) {
max_l++;
}
int ans = max(max_l, max_r);
if (max_l > max_r) {
SP[ans] = 'P';
} else {
SP[ans] = 'S';
}
for (int i = 1; i <= ans - 1; i++) {
SP[i] = (max_l > max_r ? 'S' : 'P');
}
for (int i = 1; i <= ans; i++) {
cout << SP[i];
}
cout << ".";
return 0;
} else {
fun();
return 0;
// not divide
int last = (n + 1) / 2;
string part2 = "";
int cur = (a[(n + 1) / 2] <= (n + 1) / 2);
int cover = 1 + n % 2;
while (cntl > 0 || cntr > 0) {
if (cur == 0) {
cntl -= cover;
part2 += 'S';
} else {
cntr -= cover;
part2 += 'P';
}
cur ^= 1;
cover++;
}
}
return 0;
}
/*
9
3 2 4 1 5 6 7 9 8
*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5488kb
input:
3 1 2 3
output:
.
result:
ok OK 0 operations
Test #2:
score: 0
Accepted
time: 0ms
memory: 5540kb
input:
2 2 1
output:
PS.
result:
ok OK 2 operations
Test #3:
score: 0
Accepted
time: 1ms
memory: 5480kb
input:
9 3 2 4 1 5 6 7 9 8
output:
SSSP.
result:
ok OK 4 operations
Test #4:
score: 0
Accepted
time: 1ms
memory: 5468kb
input:
10 2 9 5 7 10 6 3 1 8 4
output:
PPPPSPSP.
result:
ok OK 8 operations
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3508kb
input:
13 9 8 5 4 3 2 1 13 12 11 10 7 6
output:
SSSSSSPSP.
result:
wrong answer Jury (8) found answer better than participant (9)