Submission #1119426

#TimeUsernameProblemLanguageResultExecution timeMemory
1119426ezzzayNivelle (COCI20_nivelle)C++14
0 / 110
5 ms592 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...