結果

問題 No.1051 PQ Permutation
ユーザー IKyoproIKyopro
提出日時 2020-05-08 22:59:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,876 bytes
コンパイル時間 2,250 ms
コンパイル使用メモリ 211,376 KB
実行使用メモリ 22,912 KB
最終ジャッジ日時 2024-07-05 19:56:27
合計ジャッジ時間 12,531 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 2 ms
5,376 KB
testcase_09 WA -
testcase_10 AC 2 ms
5,376 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 314 ms
22,784 KB
testcase_16 AC 338 ms
22,656 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 444 ms
22,784 KB
testcase_21 AC 434 ms
22,784 KB
testcase_22 WA -
testcase_23 AC 425 ms
22,784 KB
testcase_24 AC 445 ms
22,912 KB
testcase_25 AC 20 ms
5,376 KB
testcase_26 WA -
testcase_27 AC 3 ms
5,376 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 19 ms
5,376 KB
testcase_31 AC 6 ms
5,376 KB
testcase_32 AC 17 ms
5,376 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 126 ms
12,928 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:56:5: warning: control reaches end of non-void function [-Wreturn-type]
   56 |     };
      |     ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,P,Q;
    cin >> N >> P >> Q;
    P--; Q--;
    vec<int> A(N);
    set<int> s;
    for(int i=0;i<N;i++){
        cin >> A[i];
        A[i]--;
        s.insert(i);
    }

    auto ok = [&](int x){
        bool p = false,q = false;
        set<int> now = s;
        for(int i=0;i<x;i++){
            if(A[i]==Q && !p) return false;
            p |= A[i]==P;
            q |= A[i]==Q;
            now.erase(i);
        }
        if(p && q) return true;
        if(!p && !q){
            for(int i=x;i<N;i++){
                int ma = *now.rbegin();
                if(ma==A[i]){
                    now.erase(ma);
                    if(ma==Q) return false;
                }
                else{
                    auto ne = now.lower_bound(A[i]);
                    if(*ne==Q) ne++;
                    if(ne==now.end()) return false;
                    return true;
                }
            }
            return false;
        }else if(p && !q){
            for(int i=x;i<N;i++){
                int ma = *now.rbegin();
                if(ma!=A[i]) return true;
                now.erase(ma);
            }
            return false;
        }
    };

    int l = -1,r = N;
    while(l+1<r){
        int m = (l+r)/2;
        (ok(m)? l:r) = m;
    }
    if(l<0){
        cout << -1 << "\n";
        return 0;
    }
    vec<int> ans(N);
    bool p = false,q = false;
    for(int i=0;i<l;i++){
        ans[i] = A[i];
        s.erase(A[i]);
        p |= A[i]==P;
        q |= A[i]==Q;
    }
    if(!p && !q){
        bool valid = false;
        for(int i=l;i<N;i++){
            if(!valid){
                int ma = *s.rbegin();
                if(A[i]==ma){
                    ans[i] = A[i];
                }else{
                    auto ne = s.lower_bound(A[i]);
                    if(!valid){
                        if(!p && *ne==Q) ne++;
                        ans[i] = *ne;
                        valid = true;
                    }
                }
            }else{
                auto ne = s.begin();
                if(!p && *ne==Q) ne++;
                ans[i] = *ne;
            }
            s.erase(ans[i]);
            p |= ans[i]==P;
            q |= ans[i]==Q;
        }
    }else if(p && !q){
        for(int i=l;i<N;i++){
            int ma = *s.rbegin();
            if(A[i]==ma){
                ans[i] = A[i];
                s.erase(ma);
            }else{
                auto ne = s.upper_bound(A[i]);
                ans[i] = *ne;
                s.erase(ne);
            }
        }
    }
    for(int i=0;i<N;i++) cout << ans[i]+1 << (i!=N-1? " ":"\n");
}
0