結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | otoshigo |
提出日時 | 2024-03-08 21:19:42 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 1,145 bytes |
コンパイル時間 | 771 ms |
コンパイル使用メモリ | 85,984 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 18:55:41 |
合計ジャッジ時間 | 4,244 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include<iostream>#include<algorithm>#include<vector>#include<queue>#include<atcoder/fenwicktree>using namespace std;using ll=long long;#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;}template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;}void solve(){int N;cin>>N;vector<int>P(N);for(int i=0;i<N;i++){cin>>P[i];P[i]--;}atcoder::fenwick_tree<int>fw(N);deque<int>dq;fw.add(P[0],1);dq.push_back(P[0]);ll t=0;for(int i=1;i<N;i++){int l=fw.sum(0,P[i]),r=i-l;if(l<r)dq.push_front(P[i]),t+=l;else if(l>r)dq.push_back(P[i]),t+=r;else{if(P[i]<dq.front())dq.push_front(P[i]),t+=l;else dq.push_back(P[i]),t+=r;}fw.add(P[i],1);}cout<<t<<"\n";for(int i=0;i<N;i++)cout<<dq[i]+1<<" ";cout<<"\n";}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){solve();}}