結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | inksamurai |
提出日時 | 2024-03-08 21:41:45 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 2,000 ms |
コード長 | 1,389 bytes |
コンパイル時間 | 4,198 ms |
コンパイル使用メモリ | 267,448 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2024-09-29 19:14:22 |
合計ジャッジ時間 | 8,063 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#define int llusing namespace std;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define rng(i,c,n) for(int i=c;i<n;i++)#define fi first#define se second#define pb push_back#define all(a) a.begin(), a.end()#define sz(a) ((int) a.size())#define vec(...) vector<__VA_ARGS__>#define _3TpP2FO ios::sync_with_stdio(0),cin.tie(0);typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pii;void print(){cout<<'\n';}template<class h,class...t>void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}int op(int l,int r){return l+r;}int e(){return 0;}void slv(){int n;cin>>n;vi a(n);rep(i,n){cin>>a[i];}rep(i,n){a[i]-=1;}int ans=0;atcoder::segtree<int,op,e> seg(n);vi qs(n);rep(i,n){int v=a[i];// tavshi ro chavagdoint l=seg.prod(0,v);// boloshiint r=seg.prod(v,n);if(l==r){qs[i]=1;}else if(l<r){qs[i]=0;}else{qs[i]=2;}ans+=min(l,r);seg.set(v,1);}deque<int> dq;dq.pb(a[0]);rng(i,1,n){if(qs[i]==1){if(a[i]<dq[0]){dq.push_front(a[i]);}else{dq.pb(a[i]);}}else if(qs[i]==0){dq.push_front(a[i]);}else{dq.pb(a[i]);}}cout<<ans<<"\n";for(auto v:dq) cout<<v+1<<" ";print();}signed main(){_3TpP2FO;int __t;cin>>__t;rep(cs,__t){slv();}}