d

link

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define F(i,x,y) for(int i=x;i<=y;++i)
const int N=2e5+10;
int T,n,m,a[2][N],kmax;
void solve()
{
  kmax=0; F(i,1,max(n,m)) a[0][i]=a[1][i]=0;
  cin>>n>>m; F(i,1,n) cin>>a[0][i]; F(i,1,m) cin>>a[1][i];
  int vmin=n<m?n:m,vmax=n<m?m:n;
  while(vmax>=2&&vmin>=1)
  {
    vmax-=2,--vmin,++kmax;
    tie(vmin,vmax)=minmax(vmin,vmax);
  }
  cout<<kmax<<'\n';
  vector<pii> ch[2];
  multiset<int> p[2];
  F(i,1,n) p[0].insert(a[0][i]);
  F(j,1,m) p[1].insert(a[1][j]);
  
  int tomin=n<m?0:1,d0=0,d1=0,ans=0;
  F(i,1,kmax) 
  {
    // tomax: tomin^1
    #define all \
    int a=p[0].size()>d0?*p[0].rbegin()-*p[0].begin():0;  \
    int b=p[1].size()>d1?*p[1].rbegin()-*p[1].begin():0;  \
    if(a>b&&b) {                                          \
      int x=*p[0].rbegin(),y=*p[0].begin();               \
      p[0].erase(x),p[0].erase(y);                        \
      ch[0].pb({x,y}),++d1,ans+=x-y;                      \
    } else if(b>a&&a) {                                   \
      int x=*p[1].rbegin(),y=*p[1].begin();               \
      p[1].erase(x),p[1].erase(y);                        \
      ch[1].pb({x,y}),++d0,ans+=x-y;                      \
    } 
    all
    else {
      tomin=(int)p[0].size()-d0<(int)p[1].size()-d1?0:1;
      auto[x,y]=ch[tomin].back();ch[tomin].pop_back(); ans-=x-y,tomin?--d0:(--d1); p[tomin].insert(x),p[tomin].insert(y);
      int a1=*p[tomin^1].rbegin(),b1=*p[tomin^1].begin();
      ans+=a1-b1,tomin?++d1:(++d0); p[tomin^1].erase(a1); p[tomin^1].erase(b1); ch[tomin^1].pb({a1,b1});
      all
    }
    cout<<ans<<' ';
  }
  cout<<'\n';
}
main()
{
  cin.tie(0)->sync_with_stdio(0);
  for(cin>>T;T--;) solve();
}