fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define fu(i,a,b) for(int i=a;i<=b;++i)
  6. #define fd(i,a,b) for(int i=a;i>=b;--i)
  7. #define task "test"
  8.  
  9. const int MAXN = 1005;
  10.  
  11. int n, m;
  12. int a[MAXN], b[MAXN];
  13.  
  14. void init() {
  15.     cin >> n;
  16.     fu(i, 1, n) cin >> a[i];
  17.     cin >> m;
  18.     fu(i, 1, m) cin >> b[i];
  19.  
  20.     if(n > m) {
  21.         swap(n, m);
  22.         swap(a, b);
  23.     }
  24. }
  25.  
  26. pair<int, int> check(int len) {
  27.     map<map<int,int>, int> seen;
  28.     map<int, int> freqA;
  29.  
  30.     fu(i,1,len) freqA[a[i]]++;
  31.     seen[freqA] = 1;
  32.  
  33.     fu(i,len+1,n) {
  34.         freqA[a[i - len]]--;
  35.         if(freqA[a[i - len]] == 0) freqA.erase(a[i - len]);
  36.         freqA[a[i]]++;
  37.         seen[freqA] = i - len + 1;
  38.     }
  39.  
  40.     map<int, int> freqB;
  41.     fu(i,1,len) freqB[b[i]]++;
  42.     if(seen.count(freqB)) return {seen[freqB], 1};
  43.  
  44.     fu(i,len+1,m) {
  45.         freqB[b[i - len]]--;
  46.         if(freqB[b[i - len]] == 0) freqB.erase(b[i - len]);
  47.         freqB[b[i]]++;
  48.         if(seen.count(freqB)) return {seen[freqB], i - len + 1};
  49.     }
  50.  
  51.     return {-1, -1};
  52. }
  53.  
  54. void solve() {
  55.     int l = 0, r = n;
  56.     int bestLen = 0, bestA = -1, bestB = -1;
  57.  
  58.     while(l <= r) {
  59.         int mid = (l + r) / 2;
  60.         pair<int,int> res = check(mid);
  61.         if(res.first != -1) {
  62.             bestLen = mid;
  63.             bestA = res.first;
  64.             bestB = res.second;
  65.             l = mid + 1;
  66.         } 
  67.         else r = mid - 1;
  68.  
  69.     }
  70.  
  71.     if(bestLen == 0) cout << "0 -1 -1";
  72.     else cout << bestLen << " " << bestA << " " << bestB;
  73. }
  74.  
  75. signed main() {
  76.     ios_base::sync_with_stdio(false);
  77.     cin.tie(NULL);
  78.     if (fopen(task ".inp", "r")) freopen(task ".inp", "r", stdin), freopen(task ".out", "w", stdout);
  79.     init();
  80.     solve();
  81. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
0 -1 -1
https://ideone.com/MmAxiQ
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!