fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  4. typedef long long ll;
  5. using pii = pair<ll, ll>;
  6. const double PI = acos(-1.0);
  7. const ll mod = 1e9 + 7;
  8.  
  9. const ll N = 1000006;
  10.  
  11.  
  12. void print(vector<ll> &occ, ll lim) {
  13.     ll ans = 0;
  14.     ll mx_occ = 0;
  15.     for (ll i = 1; i <= lim; i++) {
  16.         if (mx_occ <= i * occ[i]) {
  17.             mx_occ = occ[i] * i;
  18.             ans = i;
  19.         }
  20.     }
  21.     cout << ans << "\n";
  22. }
  23.  
  24. vector<ll> prefix_function(vector<ll> &a) {
  25.     ll n = a.size();
  26.     vector<ll> lps(n);
  27.     lps[0] = 0;
  28.     for (ll i = 1; i < n; i++) {
  29.         ll j = lps[i - 1];
  30.         while (j > 0 && a[i] != a[j])
  31.             j = lps[j - 1];
  32.         if (a[i] == a[j]) lps[i] = j + 1;
  33.         else lps[i] = 0;
  34.     }
  35.     return lps;
  36. }
  37.  
  38. void count_occurence(vector<ll> &a, ll lim) {
  39.     ll n = a.size();
  40.     vector<ll> lps = prefix_function(a);
  41.  
  42.     vector<ll> occ(n + 1);
  43.     for (ll i = lim; i < n; i++)
  44.         occ[lps[i]]++;
  45.     for (ll i = n - 1; i > 0; i--)
  46.         occ[lps[i - 1]] += occ[i];
  47.     print(occ, lim);
  48. }
  49.  
  50. int main()
  51. {
  52.     FASTIO
  53.     ll T;
  54.     T = 1;
  55.     cin >> T;
  56.     for (ll cs = 1; cs <= T; cs++) {
  57.  
  58.         ll n, m;
  59.         cin >> n >> m;
  60.         vector<ll> a(n + m + 1);
  61.         for (ll i = 0; i < n; i++)cin >> a[i];
  62.         a[n] = mod;
  63.         for (ll i = n + 1; i < n + m + 1; i++)cin >> a[i];
  64.         count_occurence(a, n);
  65.     }
  66.     return 0;
  67. }
Runtime error #stdin #stdout #stderr 0.01s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/mO2etK
language:
C++14 (gcc 8.3)
created:
4 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!