Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef ll (*mif)(ll);
- const ll LIM = 1000;
- ll* read(ll s){
- ll *r = new ll[s];
- for (ll i = 0; i < s; ++i){
- cin >> r[i];
- }
- return r;
- }
- void print(ll n, ll *a){
- for (ll i = 0; i < n; ++i){
- cerr << a[i] << " ";
- }
- cerr << "\n";
- }
- void reduce(ll n, ll *a, ll m, ll *b){
- const ll EMAX = 100000;
- ll id[EMAX + 1];
- for (ll i = 0; i <= EMAX; ++i){
- id[i] = 0;
- }
- ll num = 0;
- for (ll i = 0; i < n; ++i){
- --id[a[i]];
- }
- for (ll i = 0; i < m; ++i){
- if (id[b[i]] < 0){
- id[b[i]] = ++num;
- }
- }
- for (ll i = 0; i < n; ++i){
- a[i] = (id[a[i]] > 0 ? id[a[i]] : 0);
- }
- for (ll i = 0; i < m; ++i){
- b[i] = (id[b[i]] > 0 ? id[b[i]] : 0);
- }
- }
- mif pwf[] = {
- [](ll n)->ll { return 1; },
- [](ll n)->ll { return n; },
- [](ll n)->ll { return n * n; },
- [](ll n)->ll { return n * n * n * n; }
- };
- ll* calc_psum(ll n, ll *a, ll (*f)(ll)){
- ll *r = new ll[n];
- r[0] = f(a[0]);
- for (ll i = 1; i < n; ++i){
- r[i] = r[i - 1] + f(a[i]);
- }
- return r;
- }
- ll* psum[4];
- void psum_destroy(){
- for (ll i = 0; i < 4; ++i){
- if (psum[i]){
- delete[] psum[i];
- }
- }
- }
- void psum_init(ll n, ll *a){
- for (ll i = 0; i < 4; ++i){
- psum[i] = calc_psum(n, a, pwf[i]);
- }
- }
- ll getsum(ll a, ll b, ll p){
- return a ? psum[p][b] - psum[p][a - 1] : psum[p][b];
- }
- struct mask {
- ll st;
- ll ps[4];
- bool operator < (const mask &m) const {
- if (ps[0] != m.ps[0]){
- return ps[0] > m.ps[0];
- }
- for (int i = 1; i <= 3; ++i){
- if (ps[i] != m.ps[i]){
- return ps[i] < m.ps[i];
- }
- }
- return false;
- }
- bool operator == (const mask &m){
- return !((*this) < m) && !(m < (*this));
- }
- };
- ostream& operator << (ostream &os, const mask &m){
- return os
- << m.st << " "
- << m.ps[0] << " "
- << m.ps[1] << " "
- << m.ps[2] << " "
- << m.ps[3] << " ";
- }
- mask getmask(ll a, ll b){
- mask r;
- r.st = a + 1;
- for (ll i = 0; i <= 3; ++i){
- r.ps[i] = getsum(a, b, i);
- }
- return r;
- }
- struct mask_list {
- mask *arr;
- ll s;
- };
- mask_list get_mask_list(ll n, ll *a){
- psum_init(n, a);
- mask_list res;
- mask *&r = res.arr;
- ll &rp = res.s;
- r = new mask[n * n],
- rp = 0;
- ll x = 0, y = 0;
- for (ll q = 0; q <= n; ++q){
- if (q < n && a[q]){
- continue;
- }
- y = q;
- for (ll i = x; i < y; ++i){
- for (ll j = i; j < y; ++j){
- r[rp++] = getmask(i, j);
- }
- }
- x = q + 1;
- }
- psum_destroy();
- return res;
- }
- int main(){
- freopen("anagrams2.in", "r", stdin);
- freopen("anagrams2.out", "w", stdout);
- ll n;
- cin >> n;
- ll *a = read(n);
- ll m;
- cin >> m;
- ll *b = read(m);
- reduce(n, a, m, b);
- // cerr << "\n";
- mask_list aml = get_mask_list(n, a),
- bml = get_mask_list(m, b);
- sort(aml.arr, aml.arr + aml.s);
- sort(bml.arr, bml.arr + bml.s);
- // for (ll i = 0; i < aml.s; ++i){
- // cout << aml.arr[i] << "\n";
- // }
- // cout << "\n";
- // for (ll i = 0; i < bml.s; ++i){
- // cout << bml.arr[i] << "\n";
- // }
- delete[] a;
- delete[] b;
- n = aml.s;
- m = bml.s;
- mask *A = aml.arr,
- *B = bml.arr;
- ll R = 0, X = -1, Y = -1;
- ll x = 0, y = 0;
- while (x != n && y != m){
- while (x != n && A[x] < B[y]){
- ++x;
- }
- if (x == n){
- break;
- }
- while (y != m && B[y] < A[x]){
- ++y;
- }
- if (y == m){
- break;
- }
- if (A[x] == B[y]){
- R = A[x].ps[0];
- X = A[x].st;
- Y = B[y].st;
- break;
- }
- }
- delete[] A;
- delete[] B;
- cout << R << " " << X << " " << Y;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement