fork download
copy 
  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 = 0;
  32.     ll bestDiff = 1;
  33.  
  34.     ll colorCnt[26] = {};
  35.     ll diffColor = 0;
  36.  
  37.     ll l = 0;
  38.     for (ll r = 0; r < n; ++r) {
  39.         ll c = s[r] - 'a';
  40.         if (colorCnt[c] == 0) ++diffColor;
  41.         ++colorCnt[c];
  42.  
  43.         while (l < r) {
  44.             ll cL = s[l] - 'a';
  45.             if (colorCnt[cL] > 1) {
  46.                 --colorCnt[cL];
  47.                 ++l;
  48.             } else break;
  49.         }
  50.  
  51.         ll len = r - l + 1;
  52.         ll bestLen = bestR - bestL + 1;
  53.  
  54.         // So sánh: diffColor / len < bestDiff / bestLen
  55.         if (diffColor * bestLen < bestDiff * len || 
  56.             (diffColor * bestLen == bestDiff * len && l < bestL)) {
  57.             bestL = l;
  58.             bestR = r;
  59.             bestDiff = diffColor;
  60.         }
  61.     }
  62.  
  63.     cout << bestL + 1 << " " << bestR + 1 << "\n";
  64.     return 0;
  65. }
  66.  
  67. void input() {
  68.     cin >> n;
  69.     cin >> s;
  70.     Solve();
  71. }
  72.  
  73. int main() {
  74.     ios_base::sync_with_stdio(0);
  75.     cin.tie(0);
  76.     input();
  77.  
  78.     //bool memory2;
  79.     //cerr << "\n\n\nTime: "<< 1000.0 * clock() / CLOCKS_PER_SEC << " ms";
  80.     //cerr << "\n\n\nMemory: "<< abs(&memory1 - &memory2) * 1.0 / MASK(20) <<" MB";
  81.  
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6
ananas
stdout
copy 
1 1
https://ideone.com/zyRDCi
language:
C++ (gcc 8.3)
created:
17 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!