fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename X, typename Y>
  5. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  6.  
  7. template<typename X, typename Y>
  8. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  9.  
  10. using ll = long long;
  11. using ull = unsigned long long;
  12.  
  13. const ll BASE = 1e9+7;
  14. const int N = 1e5+5;
  15.  
  16. int n, a[N];
  17. ull P[N], H[N];
  18.  
  19. ull get_hash(int l, int r) {
  20.     return H[r] - H[l - 1] * P[r - l + 1];
  21. }
  22.  
  23. void solve() {
  24.     cin >> n;
  25.     for (int i = 1; i <= n; i++) cin >> a[i];
  26.     // Subtask 3: 0 <= a_i <= 1
  27.     if (*max_element(a + 1, a + n + 1) == 1) {
  28.         int cnt[2], last[2];
  29.         for (int i = 1; i <= n; i++) {
  30.             cnt[a[i]]++;
  31.             last[a[i]] = i;
  32.         }
  33.         int best_pos = -1;
  34.         if (cnt[0] > cnt[1]) best_pos = last[0];
  35.         else if (cnt[0] < cnt[1]) best_pos = last[1];
  36.         else best_pos = n;
  37.         cout << best_pos << ' ' << best_pos << '\n';
  38.         return;
  39.     }
  40.     P[0] = 1;
  41.     for (int i = 1; i <= n; i++) {
  42.         P[i] = P[i - 1] * BASE;
  43.         H[i] = H[i - 1] * BASE + a[i];
  44.     }
  45.     int best_cnt = 0, best_len = 0, best_pos = -1;
  46.     for (int L = 1; L <= n; L++) {
  47.         unordered_map<ull, int> cnt, pos;
  48.         for (int i = L; i <= n; i++) {
  49.             ull h = get_hash(i - L + 1, i);
  50.             cnt[h]++;
  51.             pos[h] = i;
  52.         }
  53.         for (auto& [h, c] : cnt) {
  54.             int p = pos[h];
  55.             if (chmax(best_cnt, c)) best_len = L, best_pos = p;
  56.             else if (best_cnt == c) {
  57.                 if (chmax(best_len, L)) best_pos = p;
  58.                 else if (best_len == L) chmax(best_pos, p);
  59.             }
  60.         }
  61.     }
  62.     cout << best_pos - best_len + 1 << ' ' <<  best_pos << '\n';
  63. }
  64.  
  65. int main() {
  66.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  67.  
  68.     #define TASK "BAI4"
  69.     if (fopen(TASK".INP", "r")) {
  70.         freopen(TASK".INP", "r", stdin);
  71.         freopen(TASK".OUT", "w", stdout);
  72.     }
  73.  
  74.     int tests = 1; // cin >> tests;
  75.     while (tests--) solve();
  76.  
  77.     #ifdef LOCAL
  78.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  79.     #endif
  80.     return 0;
  81. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
12
3 0 4 1 9 7 5 4 1 9 7 5
stdout 
8 12
https://ideone.com/oRi77P
language:
C++14 (gcc 8.3)
created:
3 days 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!