Submission #1093843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093843		IvanGar	Martian DNA (BOI18_dna)	C++17	100 / 100	86 ms	12424 KiB

dna

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>

using namespace std;

int main() {
    
    int n, a, r;
    cin >> n >> a >> r;

    vector<int> dna(n);
    for (int i = 0; i < n; ++i) {
        cin >> dna[i];
    }

    unordered_map<int, int> required;  
    for (int i = 0; i < r; ++i) {
        int nucleobase, quantity;
        cin >> nucleobase >> quantity;
        required[nucleobase] = quantity;
    }

    
    unordered_map<int, int> current_count;
    int matched = 0;  
    int min_len = INT_MAX;  
    int start = 0;

    for (int end = 0; end < n; ++end) {
        int end_base = dna[end];
        if (required.find(end_base) != required.end()) {
            current_count[end_base]++;
            if (current_count[end_base] == required[end_base]) {
                matched++;
            }
        }

        while (matched == required.size()) {
            min_len = min(min_len, end - start + 1);
            int start_base = dna[start];
            if (required.find(start_base) != required.end()) {
                current_count[start_base]--;
                if (current_count[start_base] < required[start_base]) {
                    matched--;
                }
            }
            start++;
        }
    }

    
    if (min_len == INT_MAX) {
        cout << "impossible" << endl;
    } else {
        cout << min_len << endl;
    }

    return 0;
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:40:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while (matched == required.size()) {
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32