QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#199657#6346. Record Parityucup-team870#WA 1ms5688kbC++142.7kb2023-10-04 13:34:372023-10-04 13:34:37

Judging History

你现在查看的是最新测评结果

  • [2023-10-04 13:34:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5688kb
  • [2023-10-04 13:34:37]
  • 提交

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