Advertisement
Guest User

peremoga

a guest
Jan 17th, 2019
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.18 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef ll (*mif)(ll);
  7.  
  8. const ll LIM = 1000;
  9.  
  10. ll* read(ll s){
  11.     ll *r = new ll[s];
  12.     for (ll i = 0; i < s; ++i){
  13.         cin >> r[i];
  14.     }
  15.     return r;
  16. }
  17. void print(ll n, ll *a){
  18.     for (ll i = 0; i < n; ++i){
  19.         cerr << a[i] << " ";
  20.     }
  21.     cerr << "\n";
  22. }
  23.  
  24. void reduce(ll n, ll *a, ll m, ll *b){
  25.  
  26.     const ll EMAX = 100000;
  27.  
  28.     ll id[EMAX + 1];
  29.     for (ll i = 0; i <= EMAX; ++i){
  30.         id[i] = 0;
  31.     }
  32.  
  33.     ll num = 0;
  34.     for (ll i = 0; i < n; ++i){
  35.         --id[a[i]];
  36.     }
  37.     for (ll i = 0; i < m; ++i){
  38.         if (id[b[i]] < 0){
  39.             id[b[i]] = ++num;
  40.         }
  41.     }
  42.  
  43.     for (ll i = 0; i < n; ++i){
  44.         a[i] = (id[a[i]] > 0 ? id[a[i]] : 0);
  45.     }
  46.     for (ll i = 0; i < m; ++i){
  47.         b[i] = (id[b[i]] > 0 ? id[b[i]] : 0);
  48.     }
  49.  
  50. }
  51.  
  52. mif pwf[] = {
  53.     [](ll n)->ll { return 1; },
  54.     [](ll n)->ll { return n; },
  55.     [](ll n)->ll { return n * n; },
  56.     [](ll n)->ll { return n * n * n * n; }
  57. };
  58.  
  59. ll* calc_psum(ll n, ll *a, ll (*f)(ll)){
  60.     ll *r = new ll[n];
  61.     r[0] = f(a[0]);
  62.     for (ll i = 1; i < n; ++i){
  63.         r[i] = r[i - 1] + f(a[i]);
  64.     }
  65.     return r;
  66. }
  67.  
  68. ll* psum[4];
  69. void psum_destroy(){
  70.     for (ll i = 0; i < 4; ++i){
  71.         if (psum[i]){
  72.             delete[] psum[i];
  73.         }
  74.     }
  75. }
  76. void psum_init(ll n, ll *a){
  77.     for (ll i = 0; i < 4; ++i){
  78.         psum[i] = calc_psum(n, a, pwf[i]);
  79.     }
  80. }
  81.  
  82. ll getsum(ll a, ll b, ll p){
  83.     return a ? psum[p][b] - psum[p][a - 1] : psum[p][b];
  84. }
  85.  
  86. struct mask {
  87.     ll st;
  88.     ll ps[4];
  89.     bool operator < (const mask &m) const {
  90.         if (ps[0] != m.ps[0]){
  91.             return ps[0] > m.ps[0];
  92.         }
  93.         for (int i = 1; i <= 3; ++i){
  94.             if (ps[i] != m.ps[i]){
  95.                 return ps[i] < m.ps[i];
  96.             }
  97.         }
  98.         return false;
  99.     }
  100.     bool operator == (const mask &m){
  101.         return !((*this) < m) && !(m < (*this));
  102.     }
  103. };
  104. ostream& operator << (ostream &os, const mask &m){
  105.     return os
  106.          << m.st << " "
  107.          << m.ps[0] << " "
  108.          << m.ps[1] << " "
  109.          << m.ps[2] << " "
  110.          << m.ps[3] << " ";
  111. }
  112.  
  113. mask getmask(ll a, ll b){
  114.     mask r;
  115.     r.st = a + 1;
  116.     for (ll i = 0; i <= 3; ++i){
  117.         r.ps[i] = getsum(a, b, i);
  118.     }
  119.     return r;
  120. }
  121.  
  122. struct mask_list {
  123.     mask *arr;
  124.     ll s;
  125. };
  126. mask_list get_mask_list(ll n, ll *a){
  127.  
  128.     psum_init(n, a);
  129.  
  130.     mask_list res;
  131.     mask *&r = res.arr;
  132.     ll &rp = res.s;
  133.  
  134.     r = new mask[n * n],
  135.     rp = 0;
  136.  
  137.     ll x = 0, y = 0;
  138.     for (ll q = 0; q <= n; ++q){
  139.         if (q < n && a[q]){
  140.             continue;
  141.         }
  142.         y = q;
  143.         for (ll i = x; i < y; ++i){
  144.             for (ll j = i; j < y; ++j){
  145.                 r[rp++] = getmask(i, j);
  146.             }
  147.         }
  148.         x = q + 1;
  149.     }
  150.  
  151.     psum_destroy();
  152.  
  153.     return res;
  154.  
  155. }
  156.  
  157. int main(){
  158.  
  159.     freopen("anagrams2.in", "r", stdin);
  160.     freopen("anagrams2.out", "w", stdout);
  161.  
  162.     ll n;
  163.     cin >> n;
  164.     ll *a = read(n);
  165.  
  166.     ll m;
  167.     cin >> m;
  168.     ll *b = read(m);
  169.  
  170.     reduce(n, a, m, b);
  171.  
  172. //    cerr << "\n";
  173.  
  174.     mask_list aml = get_mask_list(n, a),
  175.               bml = get_mask_list(m, b);
  176.  
  177.     sort(aml.arr, aml.arr + aml.s);
  178.     sort(bml.arr, bml.arr + bml.s);
  179.  
  180. //    for (ll i = 0; i < aml.s; ++i){
  181. //        cout << aml.arr[i] << "\n";
  182. //    }
  183. //    cout << "\n";
  184. //    for (ll i = 0; i < bml.s; ++i){
  185. //        cout << bml.arr[i] << "\n";
  186. //    }
  187.  
  188.     delete[] a;
  189.     delete[] b;
  190.  
  191.     n = aml.s;
  192.     m = bml.s;
  193.     mask *A = aml.arr,
  194.          *B = bml.arr;
  195.  
  196.     ll R = 0, X = -1, Y = -1;
  197.  
  198.     ll x = 0, y = 0;
  199.     while (x != n && y != m){
  200.         while (x != n && A[x] < B[y]){
  201.             ++x;
  202.         }
  203.         if (x == n){
  204.             break;
  205.         }
  206.         while (y != m && B[y] < A[x]){
  207.             ++y;
  208.         }
  209.         if (y == m){
  210.             break;
  211.         }
  212.         if (A[x] == B[y]){
  213.             R = A[x].ps[0];
  214.             X = A[x].st;
  215.             Y = B[y].st;
  216.             break;
  217.         }
  218.     }
  219.  
  220.     delete[] A;
  221.     delete[] B;
  222.  
  223.     cout << R << " " << X << " " << Y;
  224.  
  225. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement