fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void solve()
  5. {
  6.     int n, p;
  7.     cin >> n >> p;
  8.  
  9.     vector <int> a(n), ans(n);
  10.  
  11.     for(int & x : a)
  12.         cin >> x;
  13.  
  14.     sort(a.begin(), a.end());
  15.     reverse(a.begin(), a.end());
  16.  
  17.     vector <long long> sum(n);
  18.  
  19.     sum[0] = a[0];
  20.     for(int i = 1; i < n; ++i)
  21.         sum[i] = a[i] + sum[i - 1];
  22.  
  23.     int minD = lower_bound(sum.begin(), sum.end(), p) - sum.begin();
  24.  
  25.     for(int i = 0; i < n; ++i)
  26.         if(i < n / 2 + n % 2)
  27.         {
  28.             if(a[0] >= p)
  29.                 ans[i] = n;
  30.             else
  31.             {
  32.                 if(i + minD >= n)
  33.                     ans[i] = 0;
  34.                 else
  35.                     ans[i] = n - (i + minD);
  36.             }
  37.         }else
  38.             ans[i] = ans[n - 1 - i];
  39.  
  40.     int K = p - a[0];
  41.  
  42.     if(K > 0)
  43.     {
  44.         int goodAns = -1;
  45.  
  46.         if(a[1] >= K)
  47.         {
  48.             int sum = 0;
  49.             for(int i = 2; i < n; ++i)
  50.             {
  51.                 sum += a[i];
  52.                 if(sum >= K)
  53.                 {
  54.                     goodAns = i + 1;
  55.                     break;
  56.                 }
  57.             }
  58.         }else
  59.         {
  60.             bool dp[K * 4] = {1};
  61.  
  62.             int sum = 0;
  63.  
  64.             for(int i = 1; i < n;)
  65.             {
  66.                 int j;
  67.                 for(j = i; j < n && a[i] == a[j]; ++j);
  68.  
  69.                 int len = j - i;
  70.  
  71.                 for(int pos = 0; pos < K * 4; ++pos)
  72.                     if(dp[pos])
  73.                     {
  74.                         int need1 = K - pos;
  75.                         int need2 = K - (sum - pos);
  76.  
  77.  
  78.                         if(need1 <= 0)
  79.                             need1 = 0;
  80.                         else
  81.                             need1 = need1 / a[i] + (need1 % a[i] ? 1 : 0);
  82.  
  83.                         if(need2 <= 0)
  84.                             need2 = 0;
  85.                         else
  86.                             need2 = need2 / a[i] + (need2 % a[i] ? 1 : 0);
  87.  
  88.                         if(need1 + need2 <= len)
  89.                         {
  90.                             int newV = need1 + need2 + (i - 1) + 1;
  91.                             goodAns = (goodAns == -1 ? newV : min(goodAns, newV));
  92.                         }
  93.                     }
  94.  
  95.                 if(goodAns != -1)
  96.                     break;
  97.  
  98.                 for(int step = 0; step < len; ++step)
  99.                 {
  100.                     sum += a[i];
  101.  
  102.                     for(int pos = sum - a[i]; pos >= 0; --pos)
  103.                         if(dp[pos])
  104.                             dp[pos + a[i]] = true;
  105.                 }
  106.  
  107.                 i = j;
  108.             }
  109.         }
  110.  
  111.  
  112.         if(goodAns != -1)
  113.         {
  114.             goodAns = n - goodAns + 2;
  115.             for(int i = 0; i < n / 2 + n % 2; ++i)
  116.                 if(ans[i] < goodAns)
  117.                     ans[i] = ans[n - 1 - i] = goodAns;
  118.         }
  119.     }
  120.  
  121.     for(int x : ans)
  122.         cout << x << ' ';
  123.     cout << '\n';
  124. }
  125.  
  126. int main()
  127. {
  128. //    freopen("input.txt", "r", stdin);
  129.     ios_base :: sync_with_stdio(false);
  130.     cin.tie(NULL);
  131.  
  132.     int t;
  133.     cin >> t;
  134.  
  135.     while(t--)
  136.         solve();
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0s 4488KB
comments (?)
stdin
copy 
2
3 4
2 1 2
4 5
1 1 1 1
stdout
copy 
2 1 2 
0 0 0 0
https://ideone.com/ud4iTe
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!