oj.uz

Submission #198069

# Submission time Handle Problem Language Result Execution time Memory
198069 2020-01-24T15:26:02 Z heon Nivelle (COCI20_nivelle) C++17
110 / 110
 49 ms 632 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
int ctz(int x) { return __builtin_ctz(x); }
int clz(int x) { return __builtin_clz(x); }

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  #ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

  int n;
  string s;
  cin >> n >> s;
  ld res = 2.0;
  int A = 0, B = 0;
  for(int x = 1; x <= 26; x++){
    vi has(26);
    int cnt = 0;
    int r = 0;
    for(int i = 0; i < n; i++){
      while(r < n && cnt <= x){
        if(!has[s[r] - 'a']){
          if(cnt + 1 > x) break;
          cnt++;
        }
        has[s[r++] - 'a']++;
      }
      //cout << i << " -> " << r << endl;
      if((ld) x / (ld) (r - i) < res){
        res = (ld) x / (ld) (r - i);
        A = i;
        B = r - 1;
      }
      if(has[s[i] - 'a'] == 1){
        cnt--;
      }
      has[s[i] - 'a']--;
    }
  }
  cout << A + 1 << " " << B + 1;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 504 KB Output is correct
2 Correct 27 ms 504 KB Output is correct
3 Correct 36 ms 504 KB Output is correct
4 Correct 30 ms 504 KB Output is correct
5 Correct 28 ms 628 KB Output is correct
6 Correct 32 ms 592 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 504 KB Output is correct
2 Correct 27 ms 504 KB Output is correct
3 Correct 30 ms 504 KB Output is correct
4 Correct 28 ms 508 KB Output is correct
5 Correct 31 ms 632 KB Output is correct
6 Correct 28 ms 504 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 508 KB Output is correct
2 Correct 41 ms 632 KB Output is correct
3 Correct 42 ms 632 KB Output is correct
4 Correct 46 ms 504 KB Output is correct
5 Correct 49 ms 604 KB Output is correct
6 Correct 45 ms 508 KB Output is correct