SHARE
TWEET

Untitled

a guest Sep 22nd, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define uint unsigned int
  2. void substraction(vector < uint > &a, vector < uint > &b) {
  3.     if (b.size() > a.size()) {
  4.         while(a.size() != b.size()) {
  5.             a.pb(0);
  6.         }
  7.     }
  8.     fori(min(a.size(), b.size())) {
  9.         a[i] -= b[i];
  10.     }
  11. }
  12. void sum(vector < uint > &a, vector < uint > &b) {
  13.     if (a.size() < b.size()) {
  14.         fori(b.size() - a.size()) a.pb(0);
  15.     }
  16.     fori(min(a.size(), b.size())) a[i] += b[i];
  17. }
  18. void multiply(vector < uint > &a, vector < uint > &b, vector < uint > &res) {
  19.  
  20.     if (a.size() == 1) {
  21.         res = b;
  22.         fori(b.size()) res[i] *= a[0];
  23.         return ;
  24.     }
  25.     if (b.size() == 1) {
  26.         res = a;
  27.         fori(a.size()) res[i] *= b[0];
  28.         return ;
  29.     }
  30.     if (a.size() * b.size() <= 10) {
  31.         res.resize(a.size() + b.size() - 1);
  32.         for (int i = 0; i < a.size(); i++) {
  33.             for (int j = 0; j < b.size(); j++) {
  34.                 res[i + j] += (a[i] * b[j]);
  35.             }
  36.         }
  37.         return ;
  38.     }
  39.     if (a.size() > b.size()) {
  40.         while (a.size() != b.size()) b.pb(0);
  41.     } else if (a.size() < b.size()) {
  42.         while (a.size() != b.size()) a.pb(0);
  43.     }
  44.     int m = (a.size() + 1) / 2;
  45.     vector < uint > a0, a1, b0, b1;
  46.     vector < uint > a0b0, a1b1;
  47.     a0.resize(m);
  48.     b0.resize(m);
  49.     a1.resize(a.size() - m);
  50.     b1.resize(b.size() - m);
  51.     for (int i = 0; i < m; i++) a0[i] = a[i];
  52.     for (int i = m; i < a.size(); i++) a1[i - m] = a[i];
  53.  
  54.     for (int i = 0; i < m; i++) b0[i] = b[i];
  55.     for (int i = m; i < b.size(); i++) b1[i - m] = b[i];
  56.     multiply(a0, b0, a0b0);
  57.     multiply(a1, b1, a1b1);
  58.  
  59.  
  60.     sum(a0, a1);
  61.     sum(b0, b1);
  62.     vector < uint > keks1;
  63.     multiply(a0, b0, keks1);
  64.     substraction(keks1, a0b0);
  65.     substraction(keks1, a1b1);
  66.     res.resize(a.size() + b.size() - 1);
  67.     for (int i = 0; i < a0b0.size(); i++) {
  68.         res[i] += a0b0[i];
  69.     }
  70.     for (int i = m; i - m < keks1.size(); i++) {
  71.         res[i] += keks1[i - m];
  72.     }
  73.     for (int i = 2 * m; i - 2 * m < a1b1.size(); i++) {
  74.         res[i] += a1b1[i - 2 * m];
  75.     }
  76.     while (true) {
  77.         if (res.size() == 0) break;
  78.         if (res.back() == 0) res.pop_back();
  79.         else break;
  80.     }
  81.     return ;
  82. }
  83. int main() {
  84.     vector < vector < uint > > all;
  85.     ios::sync_with_stdio(false);
  86.     string s;
  87.     int kol = 0;
  88.     while (getline(cin, s)) {
  89.         if (s == "-1") break;
  90.         all.pb({0});
  91.         fori(s.size()) {
  92.             if (s[i] == ' ') {
  93.                 all[kol].pb(0);
  94.             } else {
  95.                 all[kol][all[kol].size() - 1] *= 10ll;
  96.                 all[kol][all[kol].size() - 1] += s[i] - '0';
  97.             }
  98.         }
  99.         kol++;
  100.     }
  101.     int cnt = 1;
  102.     fori(all.size()) {
  103.         cnt += all[i].size() - 1;
  104.     }
  105.     set < pair < int, int > > sizes;
  106.     fori(all.size()) sizes.insert({all[i].size(), i});
  107.     forj(all.size() - 1) {
  108.         int a = (*sizes.begin()).ss;
  109.         sizes.erase(sizes.begin());
  110.         int b = (*sizes.begin()).ss;
  111.         sizes.erase(sizes.begin());
  112.         vector < uint > res;
  113.         multiply(all[a], all[b], res);
  114.         sizes.insert({res.size(), a});
  115.         all[a] = res;
  116.     }
  117.     int ind = (*sizes.begin()).ss;
  118.     fori(all[ind].size()) cout << all[ind][i] << " ";
  119.     fori(cnt - all[ind].size()) cout << 0 << " ";
  120.     return 0;
  121. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top