oj.uz

Submission #651084

# Submission time Handle Problem Language Result Execution time Memory
651084 2022-10-17T01:40:53 Z dooompy Martian DNA (BOI18_dna) C++17
0 / 100
 367 ms 15348 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 1348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 15348 KB Output isn't correct
2 Halted 0 ms 0 KB -