Facebook
From Innocent Hummingbird, 1 Year ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 50
  1. #include<bits/stdc++.h>
  2. using namespace std;using d=double;int f(auto b,auto p,d w){unordered_map<d,int>u;vector<d>s,A,B;for(d i:p)u[i]++;for(auto i:u)while((i.second-=2)>=0)s.push_back(i.first*2);int z=s.size(),i=0,j,k=1;vector<pair<d,vector<d>>>x(1<<z/2),y(2<<z/2);d m=DBL_MAX,n,r;for(;i<z/2;i++){for(j=0;j<k;j++)x[j+k]=x[j];for(;j<k*2;x[j++].second.push_back(s[i]/2))x[j].first+=s[i];auto _=begin(x);inplace_merge(_,_+k,_+k*2);k*=2;}for(k=1;i<z;i++){for(j=0;j<k;j++)y[j+k]=y[j];for(;j<k*2;y[j++].second.push_back(s[i]/2))y[j].first+=s[i];auto _=begin(y);inplace_merge(_,_+k,_+k*2);k*=2;}for(d f:b)for(i=0,j=(1<<z-z/2)-1;i<1<<z/2&j>=0;n>w?j--:i++){n=x[i].first+y[j].first+f;abs(n-w)<m?r=f,A=x[i].second,B=y[j].second,m=abs(n-w):0;}A.insert(end(A),&B[0],&*end(B));sort(&A[0],&*end(A));for(d i:A)cout<<i<<' ';reverse(&A[0],&*end(A));for(d i:A)cout<<i<<' ';cout<<'\n'<<r;}