fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool memory1;
  4.  
  5. typedef long long ll;
  6. typedef unsigned long long ull;
  7. typedef double dbe;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<ll> vll;
  10.  
  11. #define openFile(name) freopen((name ".inp"), "r", stdin), freopen((name ".out"), "w", stdout)
  12. #define FOR(i, a, b, x) for (ll i = (a); i <= (b); i += (x))
  13. #define ROF(i, a, b, x) for (ll i = (a); i >= (b); i += (x))
  14. #define fi first
  15. #define se second
  16. #define MASK(x) (1LL << (x))
  17. #define getBit(mask, i) (((mask) >> (i)) & 1)
  18. #define BitOn(mask) (__builtin_popcountll(mask))
  19.  
  20. const int maxN = 1e6 + 2;
  21. const ll LOG = 22;
  22. const ll INF18 = 1e18;
  23. const int INF9 = 1e9;
  24. const ll MOD = 1e9 + 7;
  25. //////////////////////////////////////////////
  26.  
  27. ll n;
  28. string s;
  29.  
  30. ll Solve() {
  31.     ll bestL = 0, bestR = n - 1;
  32.     ll colorCnt[26] = {};
  33.     ll diffColor = 0;
  34.  
  35.     ll l = 0;
  36.     for (ll r = 0; r < n; ++r) {
  37.         ll c = s[r] - 'a';
  38.         if (colorCnt[c] == 0) ++diffColor;
  39.         ++colorCnt[c];
  40.  
  41.         // Co l sao cho đoạn [l..r] là tốt nhất
  42.         while (l < r) {
  43.             ll cL = s[l] - 'a';
  44.             if (colorCnt[cL] > 1) {
  45.                 --colorCnt[cL];
  46.                 ++l;
  47.             } else break;
  48.         }
  49.  
  50.         ll len = r - l + 1;
  51.         ll bestLen = bestR - bestL + 1;
  52.         // So sánh tỉ lệ: diffColor / len < bestDiff / bestLen
  53.         // => diffColor * bestLen < bestDiff * len
  54.         ll curVal = diffColor * bestLen;
  55.         ll bestVal = (bestR - bestL + 1) * 0;
  56.         FOR (i, 0, 25, 1) {
  57.             if (colorCnt[i] > 0) ++bestVal;
  58.         }
  59.         bestVal *= len;
  60.  
  61.         if (curVal < bestVal || (curVal == bestVal && l < bestL)) {
  62.             bestL = l;
  63.             bestR = r;
  64.         }
  65.     }
  66.  
  67.     cout << bestL + 1 << " " << bestR + 1 << "\n";
  68.     return 0;
  69. }
  70.  
  71. void input() {
  72.     cin >> n;
  73.     cin >> s;
  74.     Solve();
  75. }
  76.  
  77. int main() {
  78.     ios_base::sync_with_stdio(0);
  79.     cin.tie(0);
  80.     input();
  81.  
  82.     //bool memory2;
  83.     //cerr << "\n\n\nTime: "<< 1000.0 * clock() / CLOCKS_PER_SEC << " ms";
  84.     //cerr << "\n\n\nMemory: "<< abs(&memory1 - &memory2) * 1.0 / MASK(20) <<" MB";
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
6
ananas
stdout 
1 6
https://ideone.com/03tQJ6
language:
C++ (gcc 8.3)
created:
18 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!