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{ "100000" };
  85. string str_S, str_X;
  86.  
  87. bignum_t range_val[N][N];
  88. ldouble range_ld[N][N];
  89. struct range_t {
  90.     int u, v;
  91.     inline range_t() : u(0), v(0) {}
  92.     inline range_t(int u, int v) : u(u), v(v) {}
  93.     inline const bignum_t& GetVal() const { return range_val[u][v]; }
  94.     inline operator ldouble() const { return range_ld[u][v]; }
  95.     inline void SetStatus(bool active) const;
  96.     inline bool HasLeadingZero() const { return str_S[u] != '0'; }
  97.     inline int Len() const { return v - u; }
  98. };
  99.  
  100. bignum_t S, X;
  101. int n, m;
  102. int Plus[N] = {};
  103.  
  104. uint64_t rangeset_mask[N][N][2];
  105. const int MBITS = 64;
  106. struct rangeset_t {
  107.     uint64_t a[2] = {};
  108.     inline bool Conflict(const range_t &r) {
  109.         uint64_t(&m)[2] = rangeset_mask[r.u][r.v];
  110.         return (m[0] & a[0]) || (m[1] & a[1]);
  111.     }
  112.     inline void Set(const range_t &r) {
  113.         uint64_t(&m)[2] = rangeset_mask[r.u][r.v];
  114.         a[0] |= m[0], a[1] |= m[1];
  115.     }
  116.     inline void Clear(const range_t &r) {
  117.         uint64_t(&m)[2] = rangeset_mask[r.u][r.v];
  118.         a[0] &= ~m[0], a[1] &= ~m[1];
  119.     }
  120.     inline int Find(int from, bool val) {
  121.         uint64_t x[2] = { a[0], a[1] };
  122.         if (from < MBITS) {
  123.             x[0] >>= from;
  124.             for (; from < MBITS && from < n; x[0] >>= 1, from++)
  125.                 if ((x[0] & 1) == val) return from;
  126.         }
  127.         x[1] >>= from - MBITS;
  128.         for (; from < n; x[1] >>= 1, from++)
  129.             if ((x[1] & 1) == val) return from;
  130.         return from;
  131.     }
  132.     inline bool operator[](int i) {
  133.         uint64_t &x = (i < MBITS) ? (a[0]) : (i -= MBITS, a[1]);
  134.         return (x >> i) & 1;
  135.     }
  136.     inline void GetZeros(vector<int> &v, int &t) {
  137.         int cnt = 0, k = 0; t = 0;
  138.         uint64_t x[2] = { a[0], a[1] };
  139.         REP(q, 2) {
  140.             REP(i, MBITS) {
  141.                 if (k++ >= n) goto end;
  142.                 if ((x[q] & 1) == 0) cnt++;
  143.                 else if (cnt) {
  144.                     v.push_back(cnt), t += cnt;
  145.                     cnt = 0;
  146.                 }
  147.                 x[q] >>= 1;
  148.             }
  149.         }
  150.     end:
  151.         if (cnt) v.push_back(cnt), t += cnt;
  152.     }
  153.     inline void Reset() {
  154.         a[0] = a[1] = 0;
  155.     }
  156. };
  157. rangeset_t mark;
  158.  
  159. inline void range_t::SetStatus(bool active) const {
  160.     active ? mark.Set(*this) : mark.Clear(*this);
  161.     active ? (Plus[u]++, Plus[v]++) : (Plus[u]--, Plus[v]--);
  162. }
  163.  
  164. inline void SetBitRange(uint64_t &a, int u, int v) {
  165.     a = (~((~0ull) << (v - u))) << u;
  166. }
  167. inline void InitRangeSet(int u, int v) {
  168.     uint64_t(&m)[2] = rangeset_mask[u][v];
  169.     if (u < MBITS) SetBitRange(m[0], u, min(MBITS, v));
  170.     if (v > MBITS) SetBitRange(m[1], max(u - MBITS, 0), v - MBITS);
  171. }
  172.  
  173. std::istream& operator >>(std::istream &is, bignum_t &n)
  174. {
  175.     string s; is >> s; n = s;
  176.     return is;
  177. }
  178. std::ostream& operator <<(std::ostream &os, const bignum_t &n)
  179. {
  180.     os << (string)n;
  181.     return os;
  182. }
  183.  
  184. vector<range_t> ranges;
  185. typedef vector<range_t>::iterator rit;
  186. ldouble nines[N];
  187. void Init() {
  188.     REP(i, n) {
  189.         ldouble q = str_S[i] - '0';
  190.         FOR(j, i + 1, n) {
  191.             range_val[i][j].FromStr(str_S, i, j);
  192.             range_ld[i][j] = q;
  193.             q = q * 10 + str_S[j] - '0';
  194.             if (str_S[i] != '0' && range_val[i][j] <= X) {
  195.                 ranges.emplace_back(i, j);
  196.                 InitRangeSet(i, j);
  197.             }
  198.         }
  199.     }
  200.  
  201.     struct sortr_cmp {
  202.         inline bool operator()(const range_t &a, const range_t &b) const {
  203.             return b.GetVal() < a.GetVal();
  204.         }
  205.     };
  206.     sort(ranges.begin(), ranges.end(), sortr_cmp());
  207.  
  208.     FOR(i, 0, n) nines[i] = pow<ldouble>(10, i) - 1;
  209. }
  210.  
  211. inline int FindRangeAtMost(const bignum_t &lim) {
  212.     struct findr_cmp {
  213.         inline bool operator()(const range_t &r, const bignum_t &b) {
  214.             return b < r.GetVal();
  215.         }
  216.     };
  217.     return lower_bound(ranges.begin(), ranges.end(), lim, findr_cmp())
  218.         - ranges.begin();
  219. }
  220.  
  221. const ldouble ONE = 1.000001;
  222. inline bool CheckMaxFast(const bignum_t &R, int from) {
  223.     if (R.IsZero()) return true;
  224.     while (from < (int)ranges.size() &&
  225.         mark.Conflict(ranges[from])) from++;
  226.     if (from >= (int)ranges.size()) return false;
  227.  
  228.     static vector<int> its; its.clear();
  229.     int unset_len = 0;
  230.     mark.GetZeros(its, unset_len);
  231.  
  232.     ldouble ldR = R, E = ranges[from];
  233.     int len = max(ranges[from].Len() - 1, 1);
  234.     ldouble Q = E * (unset_len / len) + nines[unset_len%len];
  235.     if (Q*ONE < ldR) return false;
  236.  
  237.     ldouble S = 0;
  238.     REP(i, its.size()) {
  239.         const int &k = its[i];
  240.         S += E * (k / len) + nines[k%len];
  241.         if (S > ldR) return true;
  242.     }
  243.     return S*ONE > ldR;
  244. }
  245.  
  246. vector<bool> visi[N];
  247. bool DFS(int p, int R) {
  248.     if (visi[p][R]) return false;
  249.     else visi[p][R] = true;
  250.     if (p == n) return R == 0;
  251.     if (mark[p]) return DFS(mark.Find(p, 0), R);
  252.  
  253.     int ed = mark.Find(p, 1);
  254.     FOR(i, p + 1, ed) {
  255.         int R2 = R - range_val[p][i][0];
  256.         if (R2 < 0) break;
  257.         if (DFS(i, R2)) {
  258.             Plus[i] = true;
  259.             return true;
  260.         }
  261.     }
  262.     return false;
  263. }
  264.  
  265. inline bool InitDFS(int R) {
  266.     REP(i, n + 1) visi[i].assign(R + 1, false);
  267.     return DFS(0, R);
  268. }
  269.  
  270. bool Try(const bignum_t &R, int from) {
  271.     if (R < EPS) return InitDFS(R[0]);
  272.  
  273.     for (int i = max(FindRangeAtMost(R), from);
  274.             i < (int)ranges.size(); i++) {
  275.         if (mark.Conflict(ranges[i])) continue;
  276.         if (!CheckMaxFast(R, i)) break;
  277.  
  278.         ranges[i].SetStatus(true);
  279.         if (Try(R - ranges[i].GetVal(), i + 1)) return true;
  280.         ranges[i].SetStatus(false);
  281.     }
  282.     return false;
  283. }
  284.  
  285. inline void Input() {
  286.     cin >> str_S >> str_X;
  287.     S = str_S, X = str_X;
  288.     n = str_S.size(), m = str_X.size();
  289. }
  290.  
  291. inline void Output() {
  292.     REP(i, n) {
  293.         if (i && Plus[i]) cout << '+';
  294.         cout << str_S[i];
  295.     }
  296.     cout << '\n';
  297. }
  298.  
  299. inline void Reset() {
  300.     FOR(i,0,n) Plus[i] = false;
  301.     mark.Reset();
  302.     ranges.clear();
  303. }
  304.  
  305. int main()
  306. {
  307.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  308.  
  309.     int T; cin >> T;
  310.     REP(i,T) {
  311.         Input();
  312.         Reset();
  313.         Init();
  314.         Try(X, 0);
  315.         Output();
  316.     }
  317.  
  318.     return 0;
  319. }
Time limit exceeded #stdin #stdout 5s 4552KB
comments (?)
stdin
copy 
1
111111111111111111111111111111111211111111111111111111111111111111311111111111111111111111111111111114111111111111111 122531659665
stdout
copy 
Standard output is empty
https://ideone.com/jEijLL
language:
C++14 (gcc 8.3)
created:
5 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!