Submission #844560

#	Time	Username	Problem	Language	Result	Execution time	Memory
844560		vjudge1	Nivelle (COCI20_nivelle)	C++17	110 / 110	216 ms	10844 KiB

nivelle

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

struct F {
  int t, b;
  F(int _t, int _b) : t(_t), b(_b) { } 
  bool operator<(F ot) {
    return t * ot.b < ot.t * b;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  string S;
  cin >> N >> S;
  constexpr int A = 26;
  vector<array<int, A>> next(N + 1);
  for (int i = 0; i < A; ++i) {
    next[N][i] = N;
  }
  for (int i = N - 1; i >= 0; --i) {
    next[i] = next[i + 1];
    next[i][S[i] - 'a'] = i;
  } 
  debug(next);
  F mn(2, 1);
  int ans_L = -1, ans_R = -1;
  for (int i = 0; i < N; ++i) {
    array<bool, A> in{};
    int size = 0;
    int r = i;
    while (r < N) {
      int go = N;
      int l = -1;
      for (int j = 0; j < A; ++j) {
        if (!in[j] && next[r][j] < go) {
          go = next[r][j];
          l = j;
        }
      }
      debug(size, i, go); 
      F me(size, go - i);
      if (size > 0 && me < mn) {
        swap(mn, me);
        ans_L = i;
        ans_R = go;
      }
      r = go;
      if (l != -1) {
        in[l] = true;
      }
      size += 1;
    }
  }
  cout << ans_L + 1 << ' ' << ans_R << '\n';
}

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