Submission #1119426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119426		ezzzay	Nivelle (COCI20_nivelle)	C++14	0 / 110	5 ms	592 KiB

nivelle

#include <iostream>
#include <string>
#include <unordered_map>
#include <limits>
using namespace std;

pair<int, int> findMinimalColorfulnessSubsequence(const string& S) {
    int N = S.size();
    unordered_map<char, int> colorFrequency;
    int uniqueColors = 0;
    int left = 0, right = 0;
    int minL = 0, minR = 0;
    double minColorfulness = numeric_limits<double>::max();

    for (right = 0; right < N; ++right) {
        char currentColor = S[right];

        // Add current toy to the window
        if (colorFrequency[currentColor] == 0) {
            uniqueColors++;
        }
        colorFrequency[currentColor]++;

        // Try to shrink the window while keeping it valid
        while (true) {
            char leftColor = S[left];
            if (colorFrequency[leftColor] > 1) {
                colorFrequency[leftColor]--;
                left++;
            } else {
                break;
            }
        }

        // Calculate colorfulness for the current window
        int windowSize = right - left + 1;
        double currentColorfulness = (double)uniqueColors / windowSize;

        // Update the result if a smaller colorfulness is found
        if (currentColorfulness < minColorfulness) {
            minColorfulness = currentColorfulness;
            minL = left;
            minR = right;
        }
    }

    // Convert to 1-based indices
    return {minL + 1, minR + 1};
}

int main() {
    int N;
    string S;

    cin >> N >> S;

    auto result = findMinimalColorfulnessSubsequence(S);
    cout << result.first << " " << result.second << endl;

    return 0;
}

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