oj.uz

Submission #844560

# Submission time Handle Problem Language Result Execution time Memory
844560 2023-09-05T14:09:12 Z vjudge1 Nivelle (COCI20_nivelle) C++17
110 / 110
 216 ms 10844 KB 
// 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 360 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 4 ms 604 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10844 KB Output is correct
2 Correct 14 ms 10844 KB Output is correct
3 Correct 14 ms 10840 KB Output is correct
4 Correct 13 ms 10844 KB Output is correct
5 Correct 12 ms 10844 KB Output is correct
6 Correct 15 ms 10844 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10844 KB Output is correct
2 Correct 26 ms 10844 KB Output is correct
3 Correct 24 ms 10844 KB Output is correct
4 Correct 25 ms 10844 KB Output is correct
5 Correct 24 ms 10844 KB Output is correct
6 Correct 26 ms 10844 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 10844 KB Output is correct
2 Correct 197 ms 10844 KB Output is correct
3 Correct 169 ms 10840 KB Output is correct
4 Correct 175 ms 10840 KB Output is correct
5 Correct 186 ms 10840 KB Output is correct
6 Correct 216 ms 10844 KB Output is correct