結果
問題 |
No.1888 Odd Insertion
|
ユーザー |
![]() |
提出日時 | 2021-09-17 20:55:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 356 ms / 2,000 ms |
コード長 | 1,385 bytes |
コンパイル時間 | 2,192 ms |
コンパイル使用メモリ | 199,356 KB |
最終ジャッジ日時 | 2025-01-24 14:29:06 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/fenwicktree> using namespace atcoder; bool isok(vector<int> &Q, vector<int> &T, int i) { return (Q.at(i) % 2 == T.at(i) % 2); } 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; } reverse(Q.begin(), Q.end()); fenwick_tree<int> fw(N); vector<int> T(N); for (int i = 0; i < N; i++) { T.at(i) = fw.sum(0, Q.at(i)); fw.add(Q.at(i), 1); } for (int i = N - 1; i >= 1; i--) { if (Q.at(i - 1) > Q.at(i) && !isok(Q, T, i - 1)) { swap(Q.at(i - 1), Q.at(i)); swap(T.at(i - 1), T.at(i)); T.at(i)++; } if (Q.at(i - 1) < Q.at(i) && !isok(Q, T, i)) { swap(Q.at(i - 1), Q.at(i)); swap(T.at(i - 1), T.at(i)); T.at(i - 1)--; } if (!isok(Q, T, i)) { cout << "No" << endl; return 0; } } if (!isok(Q, T, 0)) { cout << "No" << endl; return 0; } vector<int> X(N), Y(N); for (int i = 0; i < N; i++) { X.at(i) = P.at(Q.at(i)); Y.at(i) = Q.at(i) - T.at(i); } reverse(X.begin(), X.end()); reverse(Y.begin(), Y.end()); cout << "Yes" << endl; for (int i = 0; i < N; i++) { cout << X.at(i) + 1 << " " << Y.at(i) + 1 << endl; } }