結果
問題 |
No.2665 Minimize Inversions of Deque
|
ユーザー |
|
提出日時 | 2024-03-09 01:39:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 58 ms / 2,000 ms |
コード長 | 1,394 bytes |
コンパイル時間 | 2,184 ms |
コンパイル使用メモリ | 202,552 KB |
最終ジャッジ日時 | 2025-02-20 03:22:08 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; void solve(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int test_case; cin>>test_case; while (test_case--){ solve(); } } namespace Lib { struct BIT { vector<ll> a; int sz; BIT(int n) : sz(n), a(n + 1) {} void add(int p, ll v) { for (p += 1; p <= sz; p += p & -p) a[p] += v; } ll sum(int l, int r) { ll ret = 0; for (; r > 0; r -= r & -r) ret += a[r]; for (; l > 0; l -= l & -l) ret -= a[l]; return ret; } }; } // namespace Lib void solve(){ int N; cin>>N; vector P(N,0); for(int &i:P)cin>>i,--i; Lib::BIT S(N); for(int i=0;i<N;i++){ S.add(i,1); } vector ans(N,0); ll inv=0; for(int i=N-1;i>=0;i--){ S.add(P[i],-1); int l=S.sum(0,P[i]),r=S.sum(P[i]+1,N); inv+=min(l,r); if(l>r){ ans[P[i]]=1; }else if(l<r){ ans[P[i]]=-1; } } deque<int> ret; for(int i=0;i<N;i++){ switch(ans[P[i]]){ case 1:ret.push_back(P[i]+1);break; case -1:ret.push_front(P[i]+1);break; default: if(ret.empty()){ ret.push_back(P[i]+1); }else if(P[i]+1<ret.front()){ ret.push_front(P[i]+1); }else{ ret.push_back(P[i]+1); } } } cout<<inv<<'\n'; for(int i=0;i<N;i++)cout<<ret[i]<<(i==N-1?'\n':' '); }