結果
問題 | 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 << " ";}}