結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | twooimp2 |
提出日時 | 2024-03-09 00:35:09 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 1,069 bytes |
コンパイル時間 | 6,891 ms |
コンパイル使用メモリ | 304,280 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-09-29 21:03:49 |
合計ジャッジ時間 | 9,609 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; void IO(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); } int main(){ IO(); ll t; cin>>t; while(t--){ ll n; cin>>n; vector<ll> p(n); for(ll i=0;i<n;i++){ cin>>p[i]; p[i]--; } fenwick_tree<ll> bit(n); bit.add(p[0],1); deque<ll> dq; dq.push_back(p[0]); ll x=0; for(ll i=1;i<n;i++){ ll vl=bit.sum(0,p[i]); ll vr=i-vl; if(vl<vr){ dq.push_front(p[i]); x+=vl; }else if(vl>vr){ dq.push_back(p[i]); x+=vr; }else{ if(p[i]<dq.front()){ dq.push_front(p[i]); x+=vl; }else{ dq.push_back(p[i]); x+=vr; } } bit.add(p[i],1); } cout<<x<<endl; for(ll i=0;i<n;i++){ cout<<dq[i]+1; if(i<n-1){ cout<<" "; } } cout<<endl; } }