結果
問題 | No.1051 PQ Permutation |
ユーザー | stoq |
提出日時 | 2020-05-08 10:28:18 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 1,874 bytes |
コンパイル時間 | 776 ms |
コンパイル使用メモリ | 77,752 KB |
実行使用メモリ | 6,340 KB |
最終ジャッジ日時 | 2023-09-19 07:32:13 |
合計ジャッジ時間 | 5,102 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 1 ms
4,376 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 1 ms
4,376 KB |
testcase_15 | AC | 92 ms
6,220 KB |
testcase_16 | AC | 91 ms
6,340 KB |
testcase_17 | AC | 77 ms
6,220 KB |
testcase_18 | AC | 77 ms
6,284 KB |
testcase_19 | AC | 77 ms
6,160 KB |
testcase_20 | AC | 86 ms
6,216 KB |
testcase_21 | AC | 87 ms
6,220 KB |
testcase_22 | AC | 77 ms
6,332 KB |
testcase_23 | AC | 85 ms
6,168 KB |
testcase_24 | AC | 87 ms
6,160 KB |
testcase_25 | AC | 8 ms
4,380 KB |
testcase_26 | AC | 5 ms
4,380 KB |
testcase_27 | AC | 2 ms
4,380 KB |
testcase_28 | AC | 12 ms
4,380 KB |
testcase_29 | AC | 5 ms
4,376 KB |
testcase_30 | AC | 8 ms
4,504 KB |
testcase_31 | AC | 3 ms
4,376 KB |
testcase_32 | AC | 8 ms
4,380 KB |
testcase_33 | AC | 3 ms
4,380 KB |
testcase_34 | AC | 3 ms
4,376 KB |
testcase_35 | AC | 39 ms
4,580 KB |
testcase_36 | AC | 39 ms
4,632 KB |
testcase_37 | AC | 57 ms
5,548 KB |
testcase_38 | AC | 78 ms
6,284 KB |
testcase_39 | AC | 56 ms
5,552 KB |
testcase_40 | AC | 77 ms
6,208 KB |
testcase_41 | AC | 77 ms
6,236 KB |
testcase_42 | AC | 2 ms
4,376 KB |
testcase_43 | AC | 1 ms
4,376 KB |
testcase_44 | AC | 1 ms
4,380 KB |
testcase_45 | AC | 1 ms
4,376 KB |
testcase_46 | AC | 1 ms
4,380 KB |
testcase_47 | AC | 1 ms
4,376 KB |
testcase_48 | AC | 57 ms
5,492 KB |
コンパイルメッセージ
次のファイルから読み込み: /usr/local/gcc7/include/c++/12.2.0/string:47, 次から読み込み: /usr/local/gcc7/include/c++/12.2.0/bits/locale_classes.h:40, 次から読み込み: /usr/local/gcc7/include/c++/12.2.0/bits/ios_base.h:41, 次から読み込み: /usr/local/gcc7/include/c++/12.2.0/ios:42, 次から読み込み: /usr/local/gcc7/include/c++/12.2.0/ostream:38, 次から読み込み: /usr/local/gcc7/include/c++/12.2.0/iostream:39, 次から読み込み: main.cpp:1: メンバ関数 ‘__gnu_cxx::__normal_iterator<_Iterator, _Container> __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator+(difference_type) const [with _Iterator = int*; _Container = std::vector<int>]’ 内, inlined from ‘int main()’ at main.cpp:97:41: /usr/local/gcc7/include/c++/12.2.0/bits/stl_iterator.h:1144:47: 警告: ‘q_pos’ may be used uninitialized [-Wmaybe-uninitialized] 1144 | { return __normal_iterator(_M_current + __n); } | ^~~ main.cpp: 関数 ‘int main()’ 内: main.cpp:89:16: 備考: ‘q_pos’ はここで定義されています 89 | int p_pos, q_pos; | ^~~~~ main.cpp:89:9: 警告: ‘p_pos’ may be used uninitialized [-Wmaybe-uninitialized] 89 | int p_pos, q_pos; | ^~~~~
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int INF = 1e9; 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> Max1(n + 1), Max2(n + 1); Max1[n] = -1, Max2[n] = -2; for (int i = n; i > 0; i--) { int t = a[i - 1]; if (t > Max1[i]) { Max1[i - 1] = t; Max2[i - 1] = Max1[i]; } else if (t > Max2[i]) { Max1[i - 1] = Max1[i]; Max2[i - 1] = t; } else { Max1[i - 1] = Max1[i]; Max2[i - 1] = Max2[i]; } } //条件を満たす順列Bで、先頭i文字が一致し、a[i]!=b[i]となるものがあるか int match = -1; bool used_p = false; for (int i = 0; i < n; i++) { if (used_p) { if (Max1[i] > a[i]) match = i; } else { if ((Max1[i] > a[i] && Max1[i] != q) || Max2[i] > a[i]) match = i; } if (a[i] == p) used_p = true; else if (a[i] == q && !used_p) break; } if (match == -1) { cout << -1 << endl; return 0; } vector<int> b = a; used_p = false; for (int i = 0; i < match; i++) { if (a[i] == p) { used_p = true; break; } } int m = INF, mi = -1; for (int i = match + 1; i < n; i++) { if (a[match] < a[i] && a[i] < m && (used_p || a[i] != q)) { m = min(m, a[i]); mi = i; } } swap(b[match], b[mi]); sort(begin(b) + match + 1, end(b)); if (!used_p && p > q && m != p) { int p_pos, q_pos; for (int i = match + 1; i < n; i++) { if (b[i] == p) p_pos = i; else if (b[i] == q) q_pos = i; } rotate(begin(b) + q_pos, begin(b) + q_pos + 1, begin(b) + p_pos + 1); } for (int i = 0; i < n; i++) cout << b[i] << (i == n - 1 ? "\n" : " "); return 0; }