fork download
copy 
  1. #define _FORTIFY_SOURCE 0
  2. #pragma GCC optimize("Ofast,no-stack-protector")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define FOR(i,a,b) for(int i=(a);i<=(int)(b);i++)
  7. #define REP(i,b) for(int i=0;i<(int)(b);i++)
  8. #define FORD(i,a,b) for(int i=(a);i>=(int)(b);i--)
  9. #define REPD(i,b) for(int i=(int)(b)-1;i>=0;i--)
  10. typedef long long ll;
  11. typedef long double ldouble;
  12.  
  13. const int N = 121;
  14.  
  15. const int BASE = int(1e9);
  16. const int BASE_LG = 9;
  17. struct bignum_t {
  18.     int a[N / BASE_LG + 1], n = 0;
  19.  
  20.     inline bignum_t() {}
  21.     inline bignum_t(const char *s) { FromStr(string(s)); }
  22.     inline int& operator[](int i) { return a[i]; }
  23.     inline const int& operator[](int i) const { return a[i]; }
  24.     inline void CleanZeros() {
  25.         while (n && !a[n - 1]) n--;
  26.     }
  27.     inline bool IsZero() const { return !n; }
  28.     inline int StringToInt(const string &s, int st, int ed) {
  29.         int res = 0;
  30.         FOR(i, st, ed - 1) res = res * 10 + s[i] - '0';
  31.         return res;
  32.     }
  33.     inline void FromStr(const string &s, int first = 0, int last = -1) {
  34.         if (last == -1) last = s.size();
  35.         n = 0;
  36.         int i = last;
  37.         for (; i > first; i -= BASE_LG)
  38.             a[n++] = StringToInt(s, max(i - BASE_LG, first), i);
  39.         CleanZeros();
  40.     }
  41.     inline bignum_t& operator=(const string &s) {
  42.         FromStr(s);
  43.         return *this;
  44.     }
  45.     inline operator string() const {
  46.         stringstream ss;
  47.         REPD(i, n) {
  48.             if (i != n - 1) ss << setw(BASE_LG) << setfill('0');
  49.             ss << a[i];
  50.         }
  51.         return ss.str();
  52.     }
  53.     inline operator ldouble() const {
  54.         ldouble res = 0;
  55.         REPD(i, n) res = res * BASE + a[i];
  56.         return res;
  57.     }
  58.     inline bool operator<(const bignum_t &b) const {
  59.         if (n != b.n) return n < b.n;
  60.         REPD(i, n) if (a[i] != b[i]) return a[i] < b[i];
  61.         return false;
  62.     }
  63.     inline bool operator<=(const bignum_t &b) const {
  64.         if (n != b.n) return n < b.n;
  65.         REPD(i, n) if (a[i] != b[i]) return a[i] < b[i];
  66.         return true;
  67.     }
  68.     inline bignum_t operator-(const bignum_t &b) const {
  69.         bignum_t c; c.n = n;
  70.         int carry = 0;
  71.         REP(i, n) {
  72.             int B = (i < b.n) ? b[i] : 0;
  73.             c[i] = a[i] - B - carry, carry = 0;
  74.             if (c[i] < 0) {
  75.                 c[i] += BASE;
  76.                 carry = 1;
  77.             }
  78.         }
  79.         c.CleanZeros();
  80.         return c;
  81.     }
  82. };
  83.  
  84. const bignum_t EPS{ "5000" };
  85. string str_S, str_X;
  86.  
  87. bignum_t range_val[N][N];
  88. ldouble range_ld[N][N];
  89. int ranges_idx[N][N];
  90. struct range_t {
  91.     int u, v;
  92.     inline range_t() : u(0), v(0) {}
  93.     inline range_t(int u, int v) : u(u), v(v) {}
  94.     inline const bignum_t& GetVal() const { return range_val[u][v]; }
  95.     inline operator ldouble() const { return range_ld[u][v]; }
  96.     inline void SetStatus(bool active) const;
  97.     inline bool HasLeadingZero() const { return str_S[u] != '0'; }
  98.     inline int Len() const { return v - u; }
  99.     inline int SIdx() const { return ranges_idx[u][v]; }
  100. };
  101.  
  102. bignum_t S, X;
  103. int n, m;
  104. int Plus[N] = {};
  105.  
  106. uint64_t rangeset_mask[N][N][2];
  107. const int MBITS = 64;
  108. struct rangeset_t {
  109.     uint64_t a[2] = {};
  110.     inline bool Conflict(const range_t &r) {
  111.         uint64_t(&m)[2] = rangeset_mask[r.u][r.v];
  112.         return (m[0] & a[0]) || (m[1] & a[1]);
  113.     }
  114.     inline void Set(const range_t &r) {
  115.         uint64_t(&m)[2] = rangeset_mask[r.u][r.v];
  116.         a[0] |= m[0], a[1] |= m[1];
  117.     }
  118.     inline void Clear(const range_t &r) {
  119.         uint64_t(&m)[2] = rangeset_mask[r.u][r.v];
  120.         a[0] &= ~m[0], a[1] &= ~m[1];
  121.     }
  122.     inline int Find(int from, bool val) {
  123.         uint64_t x[2] = { a[0], a[1] };
  124.         if (from < MBITS) {
  125.             x[0] >>= from;
  126.             for (; from < MBITS && from < n; x[0] >>= 1, from++)
  127.                 if ((x[0] & 1) == val) return from;
  128.         }
  129.         x[1] >>= from - MBITS;
  130.         for (; from < n; x[1] >>= 1, from++)
  131.             if ((x[1] & 1) == val) return from;
  132.         return from;
  133.     }
  134.     inline bool operator[](int i) {
  135.         uint64_t &x = (i < MBITS) ? (a[0]) : (i -= MBITS, a[1]);
  136.         return (x >> i) & 1;
  137.     }
  138.     inline void GetZeros(vector<int> &v, int &t) {
  139.         int cnt = 0, k = 0; t = 0;
  140.         uint64_t x[2] = { a[0], a[1] };
  141.         REP(q, 2) {
  142.             REP(i, MBITS) {
  143.                 if (k++ >= n) goto end;
  144.                 if ((x[q] & 1) == 0) cnt++;
  145.                 else if (cnt) {
  146.                     v.push_back(cnt), t += cnt;
  147.                     cnt = 0;
  148.                 }
  149.                 x[q] >>= 1;
  150.             }
  151.         }
  152.     end:
  153.         if (cnt) v.push_back(cnt), t += cnt;
  154.     }
  155.     inline void Reset() {
  156.         a[0] = a[1] = 0;
  157.     }
  158. };
  159. rangeset_t mark;
  160.  
  161. inline void range_t::SetStatus(bool active) const {
  162.     active ? mark.Set(*this) : mark.Clear(*this);
  163.     active ? (Plus[u]++, Plus[v]++) : (Plus[u]--, Plus[v]--);
  164. }
  165.  
  166. inline void SetBitRange(uint64_t &a, int u, int v) {
  167.     a = (~((~0ull) << (v - u))) << u;
  168. }
  169. inline void InitRangeSet(int u, int v) {
  170.     uint64_t(&m)[2] = rangeset_mask[u][v];
  171.     if (u < MBITS) SetBitRange(m[0], u, min(MBITS, v));
  172.     if (v > MBITS) SetBitRange(m[1], max(u - MBITS, 0), v - MBITS);
  173. }
  174.  
  175. std::istream& operator >>(std::istream &is, bignum_t &n)
  176. {
  177.     string s; is >> s; n = s;
  178.     return is;
  179. }
  180. std::ostream& operator <<(std::ostream &os, const bignum_t &n)
  181. {
  182.     os << (string)n;
  183.     return os;
  184. }
  185.  
  186. vector<range_t> ranges;
  187. typedef vector<range_t>::iterator rit;
  188. ldouble nines[N];
  189. void Init() {
  190.     REP(i, n) {
  191.         ldouble q = str_S[i] - '0';
  192.         FOR(j, i + 1, n) {
  193.             range_val[i][j].FromStr(str_S, i, j);
  194.             range_ld[i][j] = q;
  195.             q = q * 10 + str_S[j] - '0';
  196.             if (str_S[i] != '0' && range_val[i][j] <= X) {
  197.                 ranges.emplace_back(i, j);
  198.                 InitRangeSet(i, j);
  199.             }
  200.         }
  201.     }
  202.  
  203.     struct sortr_cmp {
  204.         inline bool operator()(const range_t &a, const range_t &b) const {
  205.             return b.GetVal() < a.GetVal();
  206.         }
  207.     };
  208.     sort(ranges.begin(), ranges.end(), sortr_cmp());
  209.  
  210.     memset(ranges_idx, -1, sizeof ranges_idx);
  211.     REP(i, ranges.size())
  212.         ranges_idx[ranges[i].u][ranges[i].v] = i;
  213.  
  214.     FOR(i, 0, n) nines[i] = pow<ldouble>(10, i) - 1;
  215. }
  216.  
  217. inline int FindRangeAtMost(const bignum_t &lim) {
  218.     struct findr_cmp {
  219.         inline bool operator()(const range_t &r, const bignum_t &b) {
  220.             return b < r.GetVal();
  221.         }
  222.     };
  223.     return lower_bound(ranges.begin(), ranges.end(), lim, findr_cmp())
  224.         - ranges.begin();
  225. }
  226.  
  227. const ldouble ONE = 1.000001;
  228. inline bool CheckMaxFast(const bignum_t &R, int from) {
  229.     if (R.IsZero()) return true;
  230.     while (from < (int)ranges.size() &&
  231.         mark.Conflict(ranges[from])) from++;
  232.     if (from >= (int)ranges.size()) return false;
  233.  
  234.     static vector<int> its; its.clear();
  235.     int unset_len = 0;
  236.     mark.GetZeros(its, unset_len);
  237.  
  238.     ldouble ldR = R, E = ranges[from];
  239.     int len = max(ranges[from].Len() - 1, 1);
  240.     ldouble Q = E * (unset_len / len) + nines[unset_len%len];
  241.     if (Q*ONE < ldR) return false;
  242.  
  243.     ldouble S = 0;
  244.     REP(i, its.size()) {
  245.         const int &k = its[i];
  246.         S += E * (k / len) + nines[k%len];
  247.         if (S > ldR) return true;
  248.     }
  249.     return S*ONE > ldR;
  250. }
  251.  
  252. vector<bool> visi[N];
  253. bool DFS(int p, int R) {
  254.     if (visi[p][R]) return false;
  255.     else visi[p][R] = true;
  256.     if (p == n) return R == 0;
  257.     if (mark[p]) return DFS(mark.Find(p, 0), R);
  258.  
  259.     int ed = mark.Find(p, 1);
  260.     int rlen = 1, rr = R;
  261.     for (rr /= 10; rr; rr /= 10, rlen++);
  262.     FOR(i, p + 1, min(ed, p + rlen)) {
  263.         int R2 = R - range_val[p][i][0];
  264.         if (R2 < 0) break;
  265.         if (DFS(i, R2)) {
  266.             Plus[i] = true;
  267.             return true;
  268.         }
  269.     }
  270.     return false;
  271. }
  272.  
  273. inline bool InitDFS(int R) {
  274.     REP(i, n + 1) visi[i].assign(R + 1, false);
  275.     return DFS(0, R);
  276. }
  277.  
  278. bool Try(const bignum_t &R, int from) {
  279.     if (R < EPS) return InitDFS(R[0]);
  280.  
  281.     for (int i = max(FindRangeAtMost(R), from);
  282.             i < (int)ranges.size(); i++) {
  283.         if (mark.Conflict(ranges[i])) continue;
  284.         if (!CheckMaxFast(R, i)) break;
  285.  
  286.         ranges[i].SetStatus(true);
  287.         if (Try(R - ranges[i].GetVal(), i + 1)) return true;
  288.         ranges[i].SetStatus(false);
  289.     }
  290.     return false;
  291. }
  292.  
  293. inline void Input() {
  294.     cin >> str_S >> str_X;
  295.     S = str_S, X = str_X;
  296.     n = str_S.size(), m = str_X.size();
  297. }
  298.  
  299. inline void Output() {
  300.     REP(i, n) {
  301.         if (i && Plus[i]) cout << '+';
  302.         cout << str_S[i];
  303.     }
  304.     cout << '\n';
  305. }
  306.  
  307. inline void Reset() {
  308.     FOR(i,0,n) Plus[i] = false;
  309.     mark.Reset();
  310.     ranges.clear();
  311. }
  312.  
  313. int main()
  314. {
  315.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  316.  
  317.     int T; cin >> T;
  318.     REP(i,T) {
  319.         Input();
  320.         Reset();
  321.         Init();
  322.         Try(X, 0);
  323.         Output();
  324.     }
  325.  
  326.     return 0;
  327. }
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
4
15112 28
120012 33
123 123
15489001 10549
stdout
copy 
15+1+12
1+20+0+12
123
1548+9001
https://ideone.com/YC9iRe
language:
C++14 (gcc 8.3)
created:
6 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!