結果

問題 No.1888 Odd Insertion
ユーザー miscalc
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 << " ";
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0