Submission #624760

#	Time	Username	Problem	Language	Result	Execution time	Memory
624760		MilosMilutinovic	Nivelle (COCI20_nivelle)	C++14	110 / 110	63 ms	724 KiB

nivelle

/**
 *    author:  wxhtzdy
 *    created: 08.08.2022 19:06:31
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  string s;
  cin >> s;
  const int A = 26;
  vector<int> lst(A, -1);         
  pair<int, int> ans = make_pair(0, 0);
  int diff = 1;
  auto Update = [&](int p, int q, int L, int R) {
    int len = ans.second - ans.first + 1;
    // diff / len > p / q
    // diff * q > p * len
    if (diff * 1LL * q > p * 1LL * len) {
      ans.first = L;
      ans.second = R;
      diff = p;
    }
  };
  for (int i = n - 1; i >= 0; i--) {
    lst[s[i] - 'a'] = i;
    vector<int> order(A);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return lst[i] < lst[j];
    });
    int cc = 1;
    for (int j : order) {
      if (j == (int) (s[i] - 'a') || lst[j] == -1) {
        continue;
      }
      Update(cc, lst[j] - i, i, lst[j] - 1);
      cc += 1;
    }
    Update(cc, n - i, i, n - 1);
  }
  cout << ans.first + 1 << " " << ans.second + 1 << '\n';                                                           
  return 0;
}

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