結果
問題 | No.1888 Odd Insertion |
ユーザー |
![]() |
提出日時 | 2022-02-13 09:37:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 135 ms / 2,000 ms |
コード長 | 1,042 bytes |
コンパイル時間 | 2,478 ms |
コンパイル使用メモリ | 199,232 KB |
最終ジャッジ日時 | 2025-01-27 22:57:46 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/fenwicktree> using namespace atcoder; int main() { int N; cin >> N; vector<int> P(N); for (int i = 0; i < N; i++) { cin >> P.at(i); P.at(i)--; } vector<int> Q(N); for (int i = 0; i < N; i++) { Q.at(P.at(i)) = i; } fenwick_tree<int> fw(N); vector<int> X(N), Y(N); for (int i = 0; i < N - 1; i++) { int y1 = fw.sum(0, Q.at(i)); int y2 = fw.sum(0, Q.at(i + 1)); if (y1 % 2 != 0 && y2 % 2 != 0) { cout << "No" << endl; return 0; } if (y2 % 2 == 0) { if (y1 % 2 != 0 || Q.at(i) < Q.at(i + 1)) { swap(Q.at(i), Q.at(i + 1)); swap(y1, y2); } } X.at(i) = P.at(Q.at(i)); Y.at(i) = y1; fw.add(Q.at(i), 1); } X.back() = P.at(Q.back()); Y.back() = fw.sum(0, Q.back()); if (Y.back() % 2 != 0) { cout << "No"; return 0; } cout << "Yes "; for (int i = 0; i < N; i++) { cout << X.at(i) + 1 << " " << Y.at(i) + 1 << " "; } }