結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | Misuki |
提出日時 | 2024-03-08 21:23:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 3,358 bytes |
コンパイル時間 | 2,558 ms |
コンパイル使用メモリ | 203,836 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-09-29 18:57:04 |
合計ジャッジ時間 | 6,080 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#pragma GCC optimize("O2")#include <algorithm>#include <array>#include <bit>#include <bitset>#include <cassert>#include <cctype>#include <cfenv>#include <cfloat>#include <chrono>#include <cinttypes>#include <climits>#include <cmath>#include <compare>#include <complex>#include <concepts>#include <cstdarg>#include <cstddef>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <fstream>#include <functional>#include <initializer_list>#include <iomanip>#include <ios>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <map>#include <memory>#include <new>#include <numbers>#include <numeric>#include <ostream>#include <queue>#include <random>#include <ranges>#include <set>#include <span>#include <sstream>#include <stack>#include <streambuf>#include <string>#include <tuple>#include <type_traits>#include <variant>#define int ll#define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1)#define INT128_MIN (-INT128_MAX - 1)#define clock chrono::steady_clock::now().time_since_epoch().count()#ifdef DEBUG#define dbg(x) cout << (#x) << " = " << x << '\n'#else#define dbg(x)#endifnamespace R = std::ranges;namespace V = std::views;using namespace std;using ll = long long;using ull = unsigned long long;using ldb = long double;using pii = pair<int, int>;using pll = pair<ll, ll>;//#define double ldbtemplate<class T>ostream& operator<<(ostream& os, const pair<T, T> pr) {return os << pr.first << ' ' << pr.second;}template<class T, size_t N>ostream& operator<<(ostream& os, const array<T, N> &arr) {for(const T &X : arr)os << X << ' ';return os;}template<class T>ostream& operator<<(ostream& os, const vector<T> &vec) {for(const T &X : vec)os << X << ' ';return os;}template<class T>ostream& operator<<(ostream& os, const set<T> &s) {for(const T &x : s)os << x << ' ';return os;}template<class T>struct fenwickTree {const int size;vector<T> data;fenwickTree(int _size) : size(_size + 1), data(_size + 1) {}fenwickTree(vector<T> &init) : size(ssize(init) + 1), data(ssize(init) + 1) {partial_sum(init.begin(), init.end(), data.begin() + 1);for(int i = size - 1; i > 0; i--)data[i] -= data[i - (i & (-i))];}void add(int i, T d) {for(i += 1; i < size; i += i & (-i))data[i] += d;}T query(int i) {T res = T(0);for(i += 1; i > 0; i -= i & (-i))res += data[i];return res;}T query(int l, int r) {return query(r - 1) - query(l - 1);}};signed main() {ios::sync_with_stdio(false), cin.tie(NULL);int t; cin >> t;while(t--) {int n; cin >> n;vector<int> p(n);for(int &x : p) {cin >> x;x--;}deque<int> dq;dq.push_front(p[0]);fenwickTree<int> ft(n);ft.add(p[0], 1);int inv = 0;for(int i = 1; i < n; i++) {int lc = ft.query(p[i]);int rc = i - lc;inv += min(lc, rc);if (lc < rc or (lc == rc and p[i] < dq.front()))dq.push_front(p[i]);elsedq.push_back(p[i]);ft.add(p[i], 1);}cout << inv << '\n';for(int x : dq)cout << x + 1 << ' ';cout << '\n';}return 0;}