fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. inline void setmin(int &x, int y) { if (y < x) x = y; }
  7. inline void setmax(int &x, int y) { if (y > x) x = y; }
  8.  
  9. const int N = 100000;
  10. const int inf = (int)1e9 + 1;
  11.  
  12. int a[N];
  13. int min_pref[N * 3];
  14. bool dp[N];
  15. int gp[N];
  16. int res[N];
  17.  
  18. void solve(int n, int W) {
  19.   // sort the power of dragons in decreasing order.
  20.   sort(a, a + n, [](int x, int y) { return x > y; });
  21.   if (a[0] >= W) {
  22.     // If the first dragon has power greater than that of prince, then he will
  23.     // always be defeated.
  24.     for (int i = 0; i < n; i++) {
  25.       res[i] = n;
  26.     }
  27.     return;
  28.   }
  29.   // We will first find the minimum size of partition for which the sum of
  30.   // elements in both partition is greater than or equal to W.
  31.   // Since the most powerful dragon is counted in both sets, we remove its
  32.   // contribution.
  33.   W -= a[0];
  34.   // min_pref[x] = lower_bound(x)
  35.   // It means to find minimum number of dragons required to obtain a sum of
  36.   // powers greater than or equal to "x".
  37.   for (int i = 0; i < N * 3; i++) {
  38.     min_pref[i] = 0;
  39.   }
  40.   // As explained in editorial, we only consider sums till W * 3. The author
  41.   // has used a safety value of N * 3, where N = max(W) for any test case.
  42.   int sum = 0;
  43.   for (int i = 0; i < n; i++) {
  44.     sum += (i > 0 ? a[i] : 0);
  45.     if (sum + 1 >= N * 3) {
  46.       break;
  47.     }
  48.     min_pref[sum + 1] = i + 1;
  49.   }
  50.   // In the previous loop, the asnwer would be set for some value of "x" which
  51.   // can be exactly obtained. Since, the initial answer is set to 0, we do a
  52.   // max operation to get the answer for greater than or equal to "x".
  53.   for (int i = 1; i < N * 3; i++) {
  54.     min_pref[i] = max(min_pref[i - 1], min_pref[i]);
  55.   }
  56.   // min prefix that can be split into two parts with sum >= W
  57.   int ans = n;
  58.   // dp[i] = 1 deontes that there exists a partition of dragons (not necessarily
  59.   // consecutive) such that the sum of powers of dragons is exactly "i". For
  60.   // other cases it is set to 0.
  61.   for (int i = 0; i < W; i++) {
  62.     dp[i] = false;
  63.   }
  64.   // There always exists a null set meaning that sum of powers of selecting no
  65.   // dragon is 0.
  66.   dp[0] = true;
  67.   // As p[0] is already acccounted, we start seeing dragons from index 1.
  68.   int p = 1;
  69.   while (p < n) {
  70.     // If we already found a partiton of dragons into 2 parts such that sum of
  71.     // both is greater than (W - a[0]), then we can safely break as the number
  72.     // of dragons we will consider will only increase.
  73.     if (p >= ans) {
  74.       break;
  75.     }
  76.     // Find the list of dragons which have the same power. Similar to 2-pointer
  77.     // trick.
  78.     int p1 = p + 1;
  79.     while (p1 < n && a[p1] == a[p]) {
  80.       p1++;
  81.     }
  82.     // Let the 2 partitions have sums A and B. We consider A = j + a[p] * k,
  83.     // for valid j and k. We need A >= W, meaning for particular "j",
  84.     // k = ceil((W-j)/a[p]). We find shortest prefix with sum >= A + W. Based
  85.     // on these values, we update the answer.
  86.     for (int j = max(0LL, W - (ll)a[p] * (p1 - p)); j < W; j++) {
  87.       if (!dp[j]) {
  88.         // There is no partition such that sum of power of dragons is exactly "j".
  89.         continue;
  90.       }
  91.       // Extend the partiton for "j" with dragons having power a[p].
  92.       int cnt = (W - j + (a[p] - 1)) / a[p];
  93.       if (cnt > (p1 - p)) {
  94.         // We don't have enough number of a[p].
  95.         continue;
  96.       }
  97.       int need_sum = (j + a[p] * cnt) + W;
  98.       int pos = min_pref[need_sum];
  99.       // We need to consider disjoint partions. The number of dragons we take
  100.       // currenltly is (p + cnt). So if min_pref gave answer (i.e. pos) as a
  101.       // lesser value, we must increase it to consider disjoint partiton
  102.       // correctly as we know the partitions for our case.
  103.       pos = max(pos, p + cnt);
  104.       setmin(ans, pos);
  105.     }
  106.     // Update the values of "j" such that dp[j] is achievable. For this, we
  107.     // maintain another dynamic programming, gp[v] = minimal number of a[p]
  108.     // required to obtain a value of "v".
  109.     for (int j = 0; j < W; j++) {
  110.       if (dp[j]) {
  111.         // dp[j] was already obtainable without any usage of a[p]
  112.         gp[j] = 0;
  113.       }
  114.       else {
  115.         // gp[j] = (gp[j - a[p]] + 1) i.e. minimum number to obtain "j-a[p]" and
  116.         // append a[p] to it.
  117.         gp[j] = inf;
  118.         if (j >= a[p]) {
  119.           setmin(gp[j], gp[j - a[p]] + 1);
  120.         }
  121.       }
  122.       if (!dp[j]) {
  123.         // dp[j] can be obtained if we have sufficient number of a[p].
  124.         // This is because :
  125.         // 1. gp[j] = inf, then we don't have sufficient number of a[p].
  126.         // 2. "j < a[p]", then gp[j] = inf.
  127.         // 3. "j = a[p]", then yes as (p1 - p) >= 1
  128.         // 4. "j > a[p]", As dp[j] was earlier not obtainable, we tried to see
  129.         // if it can be obtained using some number of a[p]. The logic used in
  130.         // gp[j] calculation ensured that dp[j - a[p]*gp[j]] was obtainable
  131.         // as each operation successively appended a[p] to a valid sequence as
  132.         // gp[x] was not inf.
  133.         dp[j] = (gp[j] <= (p1 - p));
  134.         if (j < a[p]) {
  135.           assert(gp[j] == inf);
  136.         }
  137.         else if (j > a[p]) {
  138.           if (j > ((long long)a[p] * gp[j])) {
  139.             if (gp[j] <= (p1 - p)) {
  140.               assert(dp[j - a[p] * gp[j]]);
  141.             }
  142.           }
  143.         }
  144.       }
  145.     }
  146.     p = p1;
  147.   }
  148.   // Minimum number of dragons required on one side such that sum of power of
  149.   // dragons is greater than or equal to W.
  150.   int pos = min_pref[W];
  151.   for (int i = 0; i < n; i++) {
  152.     // In first case, 2 is subtracted as in both directions, the prince would be
  153.     // killed as we calculated the length for sum of powers >= W. But it was
  154.     // mentioned prince dies if sum of powers == W. Similarly for other case,
  155.     // since only one side is considered, we subtracted 1.
  156.     res[i] = max((ans < n ? (n - 1) - (ans - 2) : 0), max(i, n - i - 1) - (pos - 1));
  157.   }
  158. }
  159.  
  160. int main() {
  161.   ios_base::sync_with_stdio(0);
  162.   cin.tie(0);
  163.   cout.precision(20);
  164.   cout << fixed;
  165.   int T;
  166.   cin >> T;
  167.   while (T--) {
  168.     int n, W;
  169.     // Input.
  170.     cin >> n >> W;
  171.     for (int i = 0; i < n; i++) {
  172.       cin >> a[i];
  173.     }
  174.     solve(n, W);
  175.     // Output.
  176.     for (int i = 0; i < n; i++) {
  177.       cout << res[i] << (i < n - 1 ? " " : "\n");
  178.     }
  179.   }
  180.   return 0;
  181. }
Success #stdin #stdout 0.01s 4428KB
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/oOh8X3
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!