結果

問題 No.2665 Minimize Inversions of Deque
ユーザー Nzt3Nzt3
提出日時 2024-03-09 01:39:24
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 1,394 bytes
コンパイル時間 2,173 ms
コンパイル使用メモリ 208,032 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2024-09-29 21:05:19
合計ジャッジ時間 5,540 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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':' ');
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0