結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー |
|
提出日時 | 2024-03-08 21:37:26 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 113 ms / 2,000 ms |
コード長 | 1,060 bytes |
コンパイル時間 | 2,774 ms |
コンパイル使用メモリ | 251,484 KB |
実行使用メモリ | 6,912 KB |
最終ジャッジ日時 | 2024-09-29 19:01:34 |
合計ジャッジ時間 | 7,867 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; struct segt{ int sz; vector<int> nodes; segt(int n){ sz=1; while(sz<n)sz*=2; nodes.resize(sz*2); } void add(int p){ p+=sz; nodes[p]=1; while(p>1){ p>>=1; nodes[p]=nodes[2*p]+nodes[2*p+1]; } } int get(int l,int r){ l+=sz; r+=sz; int res=0; while(l<r){ if(l&1)res+=nodes[l++]; if(r&1)res+=nodes[--r]; l>>=1;r>>=1; } return res; } }; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; vector<int> p(n); for(int i=0;i<n;i++)cin>>p[i]; for(int i=0;i<n;i++)p[i]--; deque<int> deq; segt st(n); ll score=0; for(int i=0;i<n;i++){ int t=st.get(0,p[i]); if(t<i-t){ deq.push_front(p[i]+1); score+=t; }else if(t==i-t){ if(p[i]<deq.front())deq.push_front(p[i]+1); else deq.push_back(p[i]+1); score+=t; }else{ deq.push_back(p[i]+1); score+=i-t; } st.add(p[i]); } cout<<score<<endl; for(int i=0;i<n;i++){ cout<<deq[i]; if(i<n-1)cout<<" "; else cout<<endl; } } }