結果
問題 |
No.1051 PQ Permutation
|
ユーザー |
![]() |
提出日時 | 2020-05-16 15:47:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 1,118 bytes |
コンパイル時間 | 458 ms |
コンパイル使用メモリ | 47,104 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 10:43:44 |
合計ジャッジ時間 | 5,121 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <stdio.h> #include <algorithm> int ri() { int n; scanf("%d", &n); return n; } int main() { int n = ri(); int l = ri() - 1; int r = ri() - 1; int a[n]; for (auto &i : a) i = ri() - 1; auto ng = [&] () { puts("-1"); exit(0); }; if (!std::next_permutation(a, a + n)) ng(); int lpos = std::find(a, a + n, l) - a; int rpos = std::find(a, a + n, r) - a; if (lpos > rpos) { int max = -1; for (int i = n - 1; i > rpos; i--) max = std::max(max, a[i]); int i = rpos; while (i >= 0 && max <= a[i]) { if (i != rpos) max = std::max(max, a[i]); i--; } if (i == -1) ng(); int min = 1000000000, index = -1; for (int j = i + 1; j < n; j++) if (a[j] > a[i] && j != rpos && min > a[j]) min = a[j], index = j; std::swap(a[i], a[index]); std::sort(a + i + 1, a + n); bool l_found = false; bool r_bury = false; int head = 0; for (auto j : a) { if (j == l) { l_found = true; a[head++] = l; if (r_bury) a[head++] = r; } else if (j == r && !l_found) r_bury = true; else a[head++] = j; } } for (auto i : a) printf("%d ", i + 1); puts(""); return 0; }