結果
問題 | No.1051 PQ Permutation |
ユーザー |
![]() |
提出日時 | 2020-04-06 00:07:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,305 bytes |
コンパイル時間 | 1,878 ms |
コンパイル使用メモリ | 181,688 KB |
実行使用メモリ | 15,104 KB |
最終ジャッジ日時 | 2024-07-05 19:32:30 |
合計ジャッジ時間 | 8,301 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 RE * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define all(x) (x).begin(), (x).end()vector<int> solve(vector<int> &A, int P, int Q) {int N = A.size();vector<int> B = A, A_i(N + 1);for(int i = 0; i < N; i++) {A_i[A[i]] = i;}bool p = false, q = false;set<int> S;for(int i = N - 1; i >= 0; i--) {p |= A[i] == P;q |= A[i] == Q;if (((A_i[P] < A_i[Q] && A_i[Q] < i) || ((!p) && q)) && S.lower_bound(A[i]) != S.end()) {int m = *S.lower_bound(A[i]);swap(B[i], B[A_i[m]]);sort(B.begin() + i + 1, B.end());break;}if (p && q && S.lower_bound(A[i]) != S.end()) {int m = *S.lower_bound(A[i]);if (m == Q) {if (next(S.lower_bound(A[i]), 1) == S.end()) {S.insert(A[i]);continue;}m = *next(S.lower_bound(A[i]), 1);}swap(B[i], B[A_i[m]]);sort(B.begin() + i + 1, B.end());if (P > Q && m != P) {auto p_it = find(all(B), P);auto q_it = find(all(B), Q);rotate(q_it, q_it + 1, p_it + 1);}break;}S.insert(A[i]);}return B;}void validate(vector<int> &A, vector<int> &B, int P, int Q) {int N = A.size();assert(N >= 2 && N <= 100000);assert(P >= 1 && P <= N && Q >= 1 && Q <= N);assert(P != Q);vector<int> A_i(N + 1, -1);for(int i = 0; i < N; i++) {assert(A_i[A[i]] == -1);A_i[A[i]] = i;}assert(A.size() == B.size() && B.size() >= 2);if (A == B) return;assert(A < B);vector<int> B_i(N + 1, -1);for(int i = 0; i < N; i++) {assert(B_i[B[i]] == -1);B_i[B[i]] = i;}assert(B_i[P] < B_i[Q]);}int main() {int N, P, Q;cin >> N >> P >> Q;vector<int> A(N);for(int i = 0; i < N; i++) {cin >> A[i];}vector<int> B = solve(A, P, Q);validate(A, B, P, Q);if (A == B) {cout << -1 << endl;} else {for(int i = 0; i < N; i++) {cout << B[i];if (i != N - 1) cout << " "; else cout << endl;}}return 0;}