結果

問題 No.1888 Odd Insertion
ユーザー 👑 emthrm
提出日時 2022-03-25 23:05:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,109 bytes
コンパイル時間 2,207 ms
コンパイル使用メモリ 203,996 KB
最終ジャッジ日時 2025-01-28 12:30:55
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 14 WA * 23
権限があれば一括ダウンロードができます

ソースコード

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

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << fixed << setprecision(20);
}
} iosetup;
template <typename Abelian>
struct FenwickTree {
explicit FenwickTree(const int n, const Abelian ID = 0)
: n(n), ID(ID), data(n, ID) {}
void add(int idx, const Abelian val) {
for (; idx < n; idx |= idx + 1) {
data[idx] += val;
}
}
Abelian sum(int idx) const {
Abelian res = ID;
for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) {
res += data[idx];
}
return res;
}
Abelian sum(const int left, const int right) const {
return left < right ? sum(right) - sum(left) : ID;
}
Abelian operator[](const int idx) const { return sum(idx, idx + 1); }
int lower_bound(Abelian val) const {
if (val <= ID) return 0;
int res = 0, exponent = 1;
while (exponent <= n) exponent <<= 1;
for (int mask = exponent >> 1; mask > 0; mask >>= 1) {
const int idx = res + mask - 1;
if (idx < n && data[idx] < val) {
val -= data[idx];
res += mask;
}
}
return res;
}
private:
const int n;
const Abelian ID;
std::vector<Abelian> data;
};
template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery {
explicit FenwickTreeSupportingRangeAddQuery(
const int n_, const Abelian ID = 0)
: n(n_ + 1), ID(ID) {
data_const.assign(n, ID);
data_linear.assign(n, ID);
}
void add(int left, const int right, const Abelian val) {
if (right < ++left) return;
for (int i = left; i < n; i += i & -i) {
data_const[i] -= val * (left - 1);
data_linear[i] += val;
}
for (int i = right + 1; i < n; i += i & -i) {
data_const[i] += val * right;
data_linear[i] -= val;
}
}
Abelian sum(const int idx) const {
Abelian res = ID;
for (int i = idx; i > 0; i -= i & -i) {
res += data_linear[i];
}
res *= idx;
for (int i = idx; i > 0; i -= i & -i) {
res += data_const[i];
}
return res;
}
Abelian sum(const int left, const int right) const {
return left < right ? sum(right) - sum(left) : ID;
}
Abelian operator[](const int idx) const { return sum(idx, idx + 1); }
private:
const int n;
const Abelian ID;
std::vector<Abelian> data_const, data_linear;
};
int main() {
int n; cin >> n;
vector<int> p(n); REP(i, n) cin >> p[i], --p[i];
vector<int> inv(n);
REP(i, n) inv[p[i]] = i;
FenwickTree<int> bit(n);
FenwickTreeSupportingRangeAddQuery<ll> idx(n);
REP(i, n) idx.add(i + 1, n, 1);
vector<int> x, y;
auto op = [&](int i) -> void {
x.emplace_back(i);
y.emplace_back(idx[inv[i]]);
idx.add(inv[i], n, -1);
};
for (int i = n - 1; i >= 0;) {
int j = i;
for (int l = -1, r = n; j >= 0; --j) {
if (l < inv[j] && inv[j] < r && idx[inv[j]] % 2 == 1) {
op(j);
for (; i > j; --i) {
bit.add(inv[j], -1);
op(i);
}
break;
} else if ((idx[inv[j]] - bit.sum(inv[j])) % 2 == 0) {
chmax(l, inv[j]);
} else {
chmin(r, inv[j]);
}
bit.add(inv[j], 1);
}
if (j == -1) {
cout << "No\n";
return 0;
}
i = j - 1;
}
reverse(ALL(x));
reverse(ALL(y));
cout << "Yes\n";
REP(i, n) cout << x[i] + 1 << ' ' << y[i] + 1 << '\n';
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0