Submission #651084

#	Time	Username	Problem	Language	Result	Execution time	Memory
651084		dooompy	Martian DNA (BOI18_dna)	C++17	0 / 100	367 ms	15348 KiB

dna

#include <bits/stdc++.h>

using namespace std;

int states[200005];
map<int, pair<int, int>> req;
set<int> completed;
map<int, int> have;

int n, k, r;

bool move(int &idx) {
    if (completed.size() == r) return true;

    while (completed.size() < r) {
        idx++;
        if (idx > n) return false;
        have[states[idx]]++;

        if (have[states[idx]] == req[states[idx]].first) {
            completed.insert(req[states[idx]].second);
        }
    }

    return true;
}

int main() {
    cin >> n >> k >> r;

    for (int i = 1; i <= n; i++) cin >> states[i];

    for (int i = 0; i < r; i++) {
        int b, q; cin >> b >> q;
        req[b] = {q, i};
    }

    int idx = 0;
    bool able = move(idx);

    if (!able) {
        cout << "impossible";
        return 0;
    }

    int l = 1;

    int ans = (idx - l + 1);

//    cout << l << " " << idx << endl;

    while (l < n) {
        if (req[states[l]].first == have[states[idx]]) {
            completed.erase(req[states[idx]].second);
        }

        have[states[idx]]--;
        l++;

        able = move(idx);
        if (!able) break;

        ans = min(ans, idx - l + 1);
    }

    cout << ans;
}

Compilation message (stderr)

dna.cpp: In function 'bool move(int&)':
dna.cpp:13:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     if (completed.size() == r) return true;
      |         ~~~~~~~~~~~~~~~~~^~~~
dna.cpp:15:29: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     while (completed.size() < r) {
      |            ~~~~~~~~~~~~~~~~~^~~

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