Submission #198069

#	Time	Username	Problem	Language	Result	Execution time	Memory
198069		heon	Nivelle (COCI20_nivelle)	C++17	110 / 110	49 ms	632 KiB

nivelle

#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 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 25 / 25
• Subtask 5: 48 / 48