fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, from, to) for (int i = (from); i <= int(to); ++i)
  5. #define FORN(i, n) FOR(i, 0, (n) - 1)
  6. #define endl '\n'
  7. #define F first
  8. #define S second
  9.  
  10. template<typename T>
  11. bool rMin(T& v, const T& rval)
  12. {
  13.     if (rval < v) {
  14.         v = rval;
  15.         return true;
  16.     }
  17.     return false;
  18. }
  19.  
  20. template<typename T>
  21. bool rMax(T& v, const T& rval)
  22. {
  23.     if (v < rval) {
  24.         v = rval;
  25.         return true;
  26.     }
  27.     return false;
  28. }
  29.  
  30. const int N = 2e5;
  31. const int INF = 2 * (N + 1);
  32. struct Dp {
  33.     int val;
  34.     int min_open, max_open;
  35. } dp[N][2];
  36.  
  37. bool a[N];
  38. int n;
  39.  
  40. Dp merge(Dp a, Dp b)
  41. {
  42.     auto val = min(a.val, b.val);
  43.     int min_open = N + 1, max_open = 0;
  44.     auto relax = [&](Dp d){
  45.         if (val == d.val) {
  46.             rMin(min_open, d.min_open);
  47.             rMax(max_open, d.max_open);
  48.         }
  49.     };
  50.     relax(a);
  51.     relax(b);
  52.     return {val, min_open, max_open};
  53. }
  54.  
  55. pair<Dp, Dp> states(int i, int v, const int C)
  56. {
  57.     Dp open_new = dp[i - 1][!v];
  58.     open_new.val += C, ++open_new.min_open, ++open_new.max_open;
  59.     Dp cont_old = dp[i - 1][v];
  60.     return {open_new, cont_old};
  61. }
  62.  
  63. Dp calc(const int C, const int st, const int fn)
  64. {
  65.     dp[0][st] = {C, 1, 1};
  66.     dp[0][!st] = {INF, -1, -1};
  67.     dp[0][!a[0]].val += 2;
  68.     FOR(i, 1, n - 1)
  69.         FORN(v, 2) {
  70.             Dp open_new, cont_old;
  71.             tie(open_new, cont_old) = states(i, v, C);
  72.             dp[i][v] = merge(open_new, cont_old);
  73.             if (a[i] != v)
  74.                 dp[i][v].val += 2;
  75.         }
  76.     return dp[n - 1][fn];
  77. }
  78.  
  79. bool ans[N];
  80.  
  81. void mod(int& k, int st, int fn)
  82. {
  83.     if (st == fn && k % 2 == 0)
  84.         --k;
  85.     if (st != fn && k % 2 == 1)
  86.         --k;
  87. }
  88.  
  89. bool restore(const int C, int k, const int s, const int f)
  90. {
  91.     mod(k, s, f);
  92.     auto fn = calc(C, s, f);
  93.     auto val = fn.val;
  94.     if (k > fn.max_open) {
  95.         assert(C == 0);
  96.         k = fn.max_open;
  97.     }
  98.     auto check = [&val, &k](Dp d){
  99.         return d.val == val && d.min_open <= k && k <= d.max_open;
  100.     };
  101.     int i = n - 1, v = f;
  102.     for (; i != 0; --i) {
  103.         ans[i] = v;
  104.         val = dp[i][v].val;
  105.         if (a[i] != v)
  106.             val -= 2;
  107.         Dp open_new, cont_old;
  108.         tie(open_new, cont_old) = states(i, v, C);
  109.         if (check(cont_old)) {
  110.             continue;
  111.         }
  112.         if (check(open_new)) {
  113.             --k;
  114.             v = !v;
  115.             continue;
  116.         }
  117.         assert(false);
  118.     }
  119.     ans[0] = v;
  120.     return true;
  121. }
  122.  
  123.  
  124. pair<int, int> res(int st, int fn, int k)
  125. {
  126.     mod(k, st, fn);
  127.     if (k == 0)
  128.         return {INF, -1};
  129.     int l = -1, r = INF;
  130.     while (l + 1 != r) {
  131.         auto m = (l + r) / 2;
  132.         if (calc(m, st, fn).min_open > k)
  133.             l = m;
  134.         else
  135.             r = m;
  136.     }
  137.     return {calc(r, st, fn).val - k * r, r};
  138. }
  139.  
  140. void solve()
  141. {
  142.     int k;
  143.     cin >> n >> k;
  144.     FORN(i, n) {
  145.         char c;
  146.         cin >> c;
  147.         a[i] = c - '0';
  148.     }
  149.  
  150.     pair<int, int> best = {INF, -1};
  151.     int bSt = -1, bFn = -1;
  152.     FORN(st, 2) {
  153.         FORN(fn, 2) {
  154.             if (rMin(best, res(st, fn, k)))
  155.                 bSt = st, bFn = fn;
  156.         }
  157.     }
  158.  
  159.     restore(best.S, k, bSt, bFn);
  160.     FORN(i, n)
  161.         cout << ans[i];
  162.     cout << endl;
  163. }
  164.  
  165.  
  166. int main()
  167. {
  168. #ifdef MY
  169.     freopen("input.txt", "r", stdin);
  170.     freopen("output.txt", "w", stdout);
  171. #else
  172.     #define FILEIO(TASK) do { freopen(TASK".in", "r", stdin); freopen(TASK".out", "w", stdout); } while (false)
  173.     FILEIO("penguins");
  174.     ios_base::sync_with_stdio(false);
  175.     cin.tie(0);
  176. #endif // MY
  177.     int t;
  178.     cin >> t;
  179.     FOR(i, 1, t) {
  180.         solve();
  181.     }
  182. }
Runtime error #stdin #stdout 0.01s 5720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Q2l9YW
language:
C++14 (gcc 8.3)
created:
2 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!