QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#199657 | #6346. Record Parity | ucup-team870# | WA | 1ms | 5688kb | C++14 | 2.7kb | 2023-10-04 13:34:37 | 2023-10-04 13:34:37 |
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 < 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: 0
Wrong Answer
time: 1ms
memory: 5688kb
input:
5 2 4 1 2 5 3
output:
PSPS.
result:
wrong output format Expected integer, but "PSPS." found