Submission #1119424

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

nivelle

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <limits>

using namespace std;

pair<int, int> findMinColorfulnessSubsequence(int N, const string& S) {
    int bestL = 1, bestR = 1;
    double minColorfulness = 1.0;
    
    // Sliding window approach
    int left = 0;
    unordered_map<char, int> colorCount;
    
    for (int right = 0; right < N; right++) {
        // Add current toy color to window
        colorCount[S[right]]++;
        
        // Shrink window from left while possible to reduce colorfulness
        while (colorCount.size() > 1 && left < right) {
            // Remove left toy color
            colorCount[S[left]]--;
            if (colorCount[S[left]] == 0) {
                colorCount.erase(S[left]);
            }
            left++;
            
            // Recalculate colorfulness
            double currentColorfulness = 1.0 * colorCount.size() / (right - left + 1);
            
            // Update best subsequence if needed
            if (currentColorfulness < minColorfulness || 
                (currentColorfulness == minColorfulness && (right - left + 1) < (bestR - bestL + 1))) {
                minColorfulness = currentColorfulness;
                bestL = left + 1;
                bestR = right + 1;
            }
        }
    }
    
    // Final check for the last possible subsequence
    double currentColorfulness = 1.0 * colorCount.size() / (N - left);
    if (currentColorfulness < minColorfulness || 
        (currentColorfulness == minColorfulness && (N - left) < (bestR - bestL + 1))) {
        bestL = left + 1;
        bestR = N;
    }
    
    return {bestL, bestR};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    string S;
    
    cin >> N;
    cin >> S;
    
    auto [L, R] = findMinColorfulnessSubsequence(N, S);
    
    cout << L << " " << R << endl;
    
    return 0;
}

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:64:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     auto [L, R] = findMinColorfulnessSubsequence(N, S);
      |          ^

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