結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー |
|
提出日時 | 2023-12-28 21:23:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,530 bytes |
コンパイル時間 | 1,118 ms |
コンパイル使用メモリ | 86,168 KB |
最終ジャッジ日時 | 2025-02-18 15:00:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 TLE * 1 -- * 4 |
ソースコード
// TLE: square time comparision#include <deque>#include <iostream>#include <vector>#include <atcoder/fenwicktree>std::pair<long long, std::vector<int>> solve(int n, const std::vector<int>& p) {std::deque<int> a;atcoder::fenwick_tree<int> ft(n);for (int i = 0; i < n; ++i) {const int cnt_lt = ft.sum(0, p[i]);const int cnt_gt = i - cnt_lt;ft.add(p[i], 1);const bool ok_l = cnt_lt <= cnt_gt;const bool ok_r = cnt_lt >= cnt_gt;if (ok_l and ok_r) {auto b = a;a.push_back(p[i]);b.push_front(p[i]);if (b < a) a.swap(b);} else if (ok_l) {a.push_front(p[i]);} else if (ok_r) {a.push_back(p[i]);} else {assert(false);}}long long inv = 0;{atcoder::fenwick_tree<int> ft(n);for (int e : a) {inv += ft.sum(e + 1, n);ft.add(e, 1);}}return { inv, std::vector<int>(a.begin(), a.end()) };}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {int n;std::cin >> n;std::vector<int> p(n);for (auto&& e : p) std::cin >> e, --e;auto [inv, a] = solve(n, p);std::cout << inv << '\n';for (int i = 0; i < n; ++i) {if (i) std::cout << ' ';std::cout << a[i] + 1;}std::cout << '\n';}}