Submission #198990

#	Time	Username	Problem	Language	Result	Execution time	Memory
198990		virchau13	Nivelle (COCI20_nivelle)	C++17	24 / 110	1097 ms	12540 KiB

nivelle

#include <iostream>
#include <algorithm>
#include <set>
#include <deque>
#include <queue>
using namespace std;

int *arr, **occ;

int main(){
    int n;
    cin >> n;
    char c;
    arr = new int[n];
    occ = new int*[n+1];
    for(int i = 0; i < n; i++){
        cin >> c;
        arr[i] = c - 'a';
        occ[i] = new int[26];
    }
    occ[n] = new int[26];
    occ++;
    for(int i = 0; i < 26; i++) occ[-1][i] = occ[0][i] = 0;
    occ[0][arr[0]] = 1;
    for(int i = 1; i < n; i++){
        for(int j = 0; j < 26; j++){
            occ[i][j] = occ[i-1][j];
        }
        occ[i][arr[i]]++;
    }
    int ml = 0, mr = 0;
    double m = 1;
    for(int i = 0; i < n; i++){
        set<int> x;
        for(int j = i; j < n; j++){
            x.insert(arr[j]);
            if((double)x.size() / (j - i + 1) < m){
                ml = i;
                mr = j;
                m = (double)x.size() / (j - i + 1);
            }
        }
    }
    cout << (ml+1) << ' ' << (mr+1) << '\n';
}

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