結果

問題 No.1051 PQ Permutation
ユーザー IKyopro
提出日時 2020-05-08 22:59:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,876 bytes
コンパイル時間 2,390 ms
コンパイル使用メモリ 203,632 KB
最終ジャッジ日時 2025-01-10 09:10:46
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
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