fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. // #pragma GCCoptimize("O3")
  9. // #pragma GCCtarget("sse4")
  10. // #pragma GCCoptimize("unroll-loops")
  11.  
  12. #define vi vector<int>
  13. #define PB push_back
  14. #define vll vector<long long>
  15. #define ll long long
  16. #define all(x) x.begin(), x.end()
  17. #define F first
  18. #define S second
  19. #define ld long double
  20. #define vld vector<long double>
  21. #define pll pair<ll, ll>
  22. #define pii pair<int, int>
  23. #define vpii vector<pair<int, int>>
  24. #define GCD __gcd
  25. #define INT __int128
  26.  
  27. #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
  28.  
  29. const ll mod = 998244353;
  30. const ll MOD = 1e9 + 7;
  31. const ll INF = 1e18;
  32. const int inf = 1e9;
  33.  
  34. struct segtree {
  35.  
  36.     int size;
  37.     vll values;
  38.  
  39.     void init(int n){
  40.         size = 1;
  41.         while (size <= n) size *= 2ll;
  42.         values.assign(2 * size, -INF);
  43.     }
  44.  
  45.     void set(int i, ll v, int x, int lx, int rx){
  46.         if (rx - lx == 1){
  47.             values[x] = v;
  48.             return;
  49.         }
  50.         int m = (lx + rx) / 2;
  51.         if (i < m) set(i, v, 2 * x + 1, lx, m);
  52.         else set(i, v, 2 * x + 2, m, rx);
  53.         values[x] = max(values[2 * x + 1], values[2 * x + 2]);
  54.     }
  55.  
  56.     void set(int i, ll v){
  57.         set(i, v, 0, 0, size);
  58.     }
  59.  
  60.     ll calc(int l, int r, int x, int lx, int rx){
  61.         if (rx <= l || r <= lx) return -INF;
  62.         if (l <= lx && rx <= r) return values[x];
  63.         int m = (lx + rx) / 2;
  64.         return max(calc(l, r, 2 * x + 1, lx, m), calc(l, r, 2 * x + 2, m, rx));
  65.     }
  66.  
  67.     ll calc(int l, int r){
  68.         return calc(l, r, 0, 0, size);
  69.     }
  70.  
  71. };
  72.  
  73. void solve(int tst){    
  74.  
  75.     ll n, c, r;
  76.     cin >> n >> c >> r;
  77.  
  78.     vll a(n);
  79.     string ans = "";
  80.  
  81.     for (int i = 0; i < n; i++) cin >> a[i];
  82.  
  83.     ll vora_laagbe = 0, vorte_parbo = c, cur = c;
  84.  
  85.     for (int i = 0; i < n; i++){
  86.         if (a[i] > c){
  87.             cout << "Impossible\n";
  88.             return;
  89.         }
  90.         cur -= a[i];
  91.         vora_laagbe += a[i];
  92.         vorte_parbo += min(r, c - cur);
  93.         cur += min(r, c - cur);
  94.         if (vora_laagbe > vorte_parbo){
  95.             cout << "Impossible\n";
  96.             return;
  97.         }
  98.     }
  99.  
  100.     cur = c;
  101.  
  102.     stack<int> zero;
  103.  
  104.     vora_laagbe -= c;
  105.     vora_laagbe = max(vora_laagbe, 0ll);
  106.  
  107.     segtree st;
  108.     st.init(n + 10);
  109.  
  110.     vll fuel(n + 10);
  111.  
  112.  
  113.     for (int i = 0; i < n; i++){
  114.         if (cur >= a[i]){
  115.             // cout << vora_laagbe << "\n";
  116.             cur -= a[i];
  117.             if (vora_laagbe && cur + r <= c){
  118.                 cur += r;
  119.                 ans += '1';
  120.                 vora_laagbe = max(vora_laagbe - r, 0ll);
  121.             }
  122.             else if (i + 1 < n && cur < a[i + 1]){
  123.                 vora_laagbe = max(vora_laagbe - min(r, c - cur), 0ll);
  124.                 cur += min(r, c - cur);
  125.                 ans += '1';
  126.             }
  127.             else {
  128.                 ans += '0';
  129.                 zero.push(i);
  130.             }
  131.             st.set(i, cur);
  132.             fuel[i] = cur;
  133.         }
  134.         else {
  135.             if (zero.empty()) {
  136.                 cout << "Impossible\n";
  137.                 return;
  138.             }
  139.             int last = zero.top();
  140.             zero.pop();
  141.             ans[last] = '1';
  142.             ll val1 = min(r, c - fuel[last]);
  143.             ll val2 = c - st.calc(last, i);
  144.             val2 = min(val2, c);
  145.             cur += max(min(val1, val2), 0ll);
  146.             vora_laagbe -= max(min(val1, val2), 0ll);
  147.             if (cur < a[i]){
  148.                 cout << "Impossible\n";
  149.                 return;
  150.             }
  151.             i--;
  152.         }
  153.     }
  154.  
  155.     cout << ans << "\n";
  156.  
  157.  
  158. }
  159.  
  160. int main(){
  161.  
  162.     ios_base::sync_with_stdio(0);
  163.     cin.tie(0);
  164.     // pre();
  165.     int tc = 1;
  166.     cin >> tc;
  167.     for (int i = 1; i <= tc; i++){
  168.         solve(i);
  169.     }
  170.     return 0;
  171. }
  172.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
https://ideone.com/k9L3w4
language:
C++ (gcc 8.3)
created:
2 days 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!