Submission #891702

#	Time	Username	Problem	Language	Result	Execution time	Memory
891702		ind1v	Nivelle (COCI20_nivelle)	C++11	110 / 110	22 ms	1628 KiB

nivelle

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

const int N = 1e5 + 4;
const int INF = 2e18;

int a[N], c[N];
int n, cr, z, t;
string s;

struct Fr {
  int n, d;
};

bool cmp(Fr x, Fr y) {
  return (x.n * y.d > y.n * x.d);
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> s;
  for (int i = 1; i <= n; ++i) {
    a[i] = s[i - 1] - 'a';
  }
  Fr mn;
  mn.n = INF; mn.d = 1;
  for (int i = 1; i <= 26; ++i) {
    cr = 0;
    Fr f;
    for (int j = 0; j < 26; ++j) {
      c[j] = 0;
    }
    int l = 1;
    for (int r = 1; r <= n; ++r) {
      ++c[a[r]];
      if (c[a[r]] == 1) {
        ++cr;
      }
      while (cr > i) {
        --c[a[l]];
        if (c[a[l]] == 0) {
          --cr;
        }
        ++l;
      }
      f.n = i;
      f.d = r - l + 1;
      if (cmp(mn, f)) {
        z = l;
        t = r;
        mn = f;
      }
    }
  }
  cout << z << ' ' << t;
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 25 / 25
• Subtask 5: 48 / 48