fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. // State to track Capacity (C) and Remaining Budget (R)
  8. struct State {
  9.     long long C, R;
  10.  
  11.     // Sort descending by C, then descending by R
  12.     bool operator<(const State& o) const {
  13.         if (C != o.C) return C > o.C;
  14.         return R > o.R;
  15.     }
  16. };
  17.  
  18. void solve() {
  19.     long long n, m, k;
  20.     cin >> n >> m >> k;
  21.  
  22.     vector<long long> a(n);
  23.     for (int i = 0; i < n; i++) {
  24.         cin >> a[i];
  25.     }
  26.  
  27.     // Initialize the Pareto frontier
  28.     vector<State> frontier;
  29.     frontier.push_back({k, k});
  30.  
  31.     for (int i = 0; i < n; i++) {
  32.         long long req = (m - a[i]) % m;
  33.         bool can_reach_zero = false;
  34.  
  35.         for (auto& s : frontier) {
  36.             if (s.C >= req) {
  37.                 can_reach_zero = true;
  38.                 break;
  39.             }
  40.         }
  41.  
  42.         long long v_min = can_reach_zero ? 0 : a[i];
  43.         vector<State> next_states;
  44.  
  45.         if (can_reach_zero) {
  46.             for (auto& s : frontier) {
  47.                 if (s.C < req) continue;
  48.  
  49.                 long long add_prev = s.C - s.R;
  50.  
  51.                 // Find largest x1 <= add_prev
  52.                 long long x1 = -1;
  53.                 if (add_prev >= req) {
  54.                     long long k1 = (add_prev - req) / m;
  55.                     x1 = req + k1 * m;
  56.                 }
  57.  
  58.                 // Find smallest x2 >= add_prev
  59.                 long long x2 = -1;
  60.                 if (x1 == add_prev) {
  61.                     x2 = x1;
  62.                 } else {
  63.                     x2 = (x1 == -1) ? req : x1 + m;
  64.                 }
  65.  
  66.                 // Push valid branch states
  67.                 if (x1 != -1 && x1 <= s.C) {
  68.                     next_states.push_back({x1 + s.R, s.R});
  69.                 }
  70.                 if (x2 != -1 && x2 <= s.C && x2 != x1) {
  71.                     next_states.push_back({s.C, s.C - x2});
  72.                 }
  73.             }
  74.         } else {
  75.             // If we can't reach 0, minimum achievable is a[i] via x=0.
  76.             for (auto& s : frontier) {
  77.                 next_states.push_back({s.R, s.R});
  78.             }
  79.         }
  80.  
  81.         // Pareto pruning: retain strictly dominant configurations
  82.         sort(next_states.begin(), next_states.end());
  83.         frontier.clear();
  84.         long long max_R = -1;
  85.  
  86.         for (auto& s : next_states) {
  87.             if (s.R > max_R) {
  88.                 frontier.push_back(s);
  89.                 max_R = s.R;
  90.             }
  91.         }
  92.  
  93.         // Safeguard to prevent TLE, capping state space if it ever branches unusually wide.
  94.         if (frontier.size() > 600) {
  95.             vector<State> reduced;
  96.             double step = (double)frontier.size() / 500.0;
  97.             for (double idx = 0; idx < frontier.size(); idx += step) {
  98.                 reduced.push_back(frontier[(int)idx]);
  99.             }
  100.             if (reduced.back().C != frontier.back().C || reduced.back().R != frontier.back().R) {
  101.                 reduced.push_back(frontier.back());
  102.             }
  103.             frontier = reduced;
  104.         }
  105.  
  106.         a[i] = v_min;
  107.     }
  108.  
  109.     // Output sequence
  110.     for (int i = 0; i < n; i++) {
  111.         cout << a[i] << (i == n - 1 ? "" : " ");
  112.     }
  113.     cout << "\n";
  114. }
  115.  
  116. int main() {
  117.     // Fast I/O
  118.     ios_base::sync_with_stdio(false);
  119.     cin.tie(NULL);
  120.  
  121.     int t;
  122.     if (cin >> t) {
  123.         while (t--) {
  124.             solve();
  125.         }
  126.     }
  127.     return 0;
  128. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3
4 6 3
2 5 4 1
4 17 100
2 0 2 6
5 10 6
2 6 5 3 9
stdout
copy 
2 0 0 1
0 0 0 0
2 0 0 3 0
https://ideone.com/IP42yP
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!