Submission #1301452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301452		oa0605	Martian DNA (BOI18_dna)	C++20	100 / 100	22 ms	2836 KiB

dna

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // Use fast I/O to handle N up to 200,000 within the time limit
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, r;
    if (!(cin >> n >> k >> r)) return 0;

    // Read the DNA sequence
    vector<int> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];

    // Store the requirements.
    // req[b] = quantity needed for nucleobase b
    vector<int> req(k, 0);
    for(int i = 0; i < r; i++) {
        int b, q;
        cin >> b >> q;
        req[b] = q;
    }

    // Vector to store counts of nucleobases in the current window
    vector<int> cnt(k, 0);

    int i = 0; // Left pointer of the window
    int formed = 0; // How many distinct nucleobase requirements are currently satisfied
    int res = n + 1; // Initialize result to a value larger than possible (Infinity)

    // j is the Right pointer of the window
    for(int j = 0; j < n; j++)
    {
        // 1. Expand the window to the right
        int current_char = v[j];
        cnt[current_char]++;

        // If this nucleobase has a requirement and we just reached it
        if(req[current_char] > 0 && cnt[current_char] == req[current_char]) {
            formed++;
        }

        // 2. Shrink the window from the left as long as requirements are met
        while(formed == r)
        {
            // We have a valid window, update the minimum length
            res = min(res, j - i + 1);

            // Remove the leftmost character
            int left_char = v[i];
            cnt[left_char]--;

            // If the count drops below the requirement, we no longer satisfy this requirement
            if(req[left_char] > 0 && cnt[left_char] < req[left_char]) {
                formed--;
            }
            
            // Move left pointer forward
            i++;
        }
    }

    // Output the result
    if(res > n)
        cout << "impossible";
    else
        cout << res;

    return 0;
}

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