fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct State {
  8.     long long used, c;
  9.     long long S() const { return used - c; }
  10. };
  11.  
  12. void solve() {
  13.     long long n, m, k;
  14.     cin >> n >> m >> k;
  15.  
  16.     vector<long long> a(n);
  17.     for (int i = 0; i < n; i++) {
  18.         cin >> a[i];
  19.     }
  20.  
  21.     vector<State> frontier;
  22.     frontier.reserve(8005);
  23.     frontier.push_back({0, 0});
  24.  
  25.     // Static vector để tái sử dụng bộ nhớ cho mọi testcase (chống TLE do allocation)
  26.     static vector<State> list1, list2, next_states;
  27.  
  28.     for (int i = 0; i < n; i++) {
  29.         long long req = (m - a[i]) % m;
  30.         bool can_reach_zero = false;
  31.  
  32.         for (const auto& st : frontier) {
  33.             if (req <= st.c + k - st.used) {
  34.                 can_reach_zero = true;
  35.                 break;
  36.             }
  37.         }
  38.  
  39.         if (can_reach_zero) {
  40.             list1.clear();
  41.             list2.clear();
  42.  
  43.             for (const auto& st : frontier) {
  44.                 long long c = st.c;
  45.                 long long used = st.used;
  46.  
  47.                 // Phân nhánh 1: x1 <= c
  48.                 if (c >= req) {
  49.                     long long x1 = req + ((c - req) / m) * m;
  50.                     if (list1.empty() || list1.back().c != x1) {
  51.                         list1.push_back({used, x1});
  52.                     }
  53.                 }
  54.  
  55.                 // Phân nhánh 2: x2 >= c
  56.                 long long x2 = (c <= req) ? req : req + ((c - req + m - 1) / m) * m;
  57.                 long long u2 = used + x2 - c;
  58.                 if (u2 <= k) {
  59.                     if (!list2.empty() && list2.back().c == x2) {
  60.                         if (u2 < list2.back().used) list2.back().used = u2;
  61.                     } else {
  62.                         list2.push_back({u2, x2});
  63.                     }
  64.                 }
  65.             }
  66.  
  67.             // Gộp 2 list đã tự động sắp xếp bằng Two Pointers (O(F))
  68.             next_states.clear();
  69.             int p1 = 0, p2 = 0;
  70.             int sz1 = list1.size(), sz2 = list2.size();
  71.             while (p1 < sz1 || p2 < sz2) {
  72.                 if (p1 < sz1 && p2 < sz2) {
  73.                     if (list1[p1].c < list2[p2].c) next_states.push_back(list1[p1++]);
  74.                     else if (list1[p1].c > list2[p2].c) next_states.push_back(list2[p2++]);
  75.                     else {
  76.                         next_states.push_back({min(list1[p1].used, list2[p2].used), list1[p1].c});
  77.                         p1++; p2++;
  78.                     }
  79.                 } else if (p1 < sz1) {
  80.                     next_states.push_back(list1[p1++]);
  81.                 } else {
  82.                     next_states.push_back(list2[p2++]);
  83.                 }
  84.             }
  85.  
  86.             // Lọc Pareto ngặt (O(F))
  87.             frontier.clear();
  88.             for (const auto& st : next_states) {
  89.                 while (!frontier.empty() && frontier.back().used >= st.used) {
  90.                     frontier.pop_back();
  91.                 }
  92.                 if (!frontier.empty() && frontier.back().S() <= st.S()) {
  93.                     continue;
  94.                 }
  95.                 frontier.push_back(st);
  96.             }
  97.  
  98.             // Cắt tỉa thông minh (Giữ mảng đầu cuối) để khóa Memory/Time bounds
  99.             if (frontier.size() > 8000) {
  100.                 vector<State> reduced;
  101.                 reduced.reserve(8000);
  102.                 for (int j = 0; j < 4000; j++) reduced.push_back(frontier[j]);
  103.                 for (int j = 0; j < 4000; j++) reduced.push_back(frontier[frontier.size() - 4000 + j]);
  104.                 frontier = move(reduced);
  105.             }
  106.  
  107.             a[i] = 0;
  108.         } else {
  109.             // Nếu không đạt 0, state tối ưu nhất bắt buộc là giá trị cũ của A[i] 
  110.             // với lượng chi phí rẻ nhất (used cực tiểu).
  111.             long long min_used = frontier[0].used; 
  112.             frontier.clear();
  113.             frontier.push_back({min_used, 0});
  114.         }
  115.     }
  116.  
  117.     for (int i = 0; i < n; i++) {
  118.         cout << a[i] << (i == n - 1 ? "" : " ");
  119.     }
  120.     cout << "\n";
  121. }
  122.  
  123. int main() {
  124.     ios_base::sync_with_stdio(false);
  125.     cin.tie(NULL);
  126.  
  127.     int t;
  128.     if (cin >> t) {
  129.         while (t--) {
  130.             solve();
  131.         }
  132.     }
  133.     return 0;
  134. }
Success #stdin #stdout 0s 5288KB
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/oyEY9x
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!