Submission #930091

#	Time	Username	Problem	Language	Result	Execution time	Memory
930091		Karoot	Martian DNA (BOI18_dna)	C++17	100 / 100	87 ms	9556 KiB

dna

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
 
#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()
 
using namespace std;
 
typedef long long ll;
 
ll linf = 1e15+1;
 
inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}
 
const int MAXN = 2e5+1;
 
int amountOf[MAXN], needed[MAXN];
set<int> fulfilled;
bool nocares[MAXN];
 
int main(){
    scoobydoobydoo();
    int n, k, r; cin >> n >> k >> r;
    vector<int> v(n);
    for (int i = 0; i < n; i++)cin >> v[i];
 
    for (int i = 0; i < r; i++){
        int a; cin >> a;
        cin >> needed[a];
    }
 
    for (int i = 0; i <= k+1; i++){
        if (!needed[i])nocares[i] = true;
    }
 
    int i = 0, j = 1;
 
    if (!nocares[v[0]]){
        amountOf[v[0]]++;
        if (amountOf[v[0]] >= needed[v[0]])fulfilled.insert(v[0]);
    }
 
    int mini = 1e7+1;;
 
    while (i < j){
        if (j == n || fulfilled.size() == r){
            //cout << "______________________________" << endl;
            if (fulfilled.size() == r) mini = min(mini, j-i);
            if (!nocares[v[i]]){
                amountOf[v[i]]--;
                if (amountOf[v[i]] < needed[v[i]]){
                    auto it = fulfilled.find(v[i]);
                    if (it != fulfilled.end() && (*it) == v[i]){
                        fulfilled.erase(it);
                    }
                }
            }
            i++;
        } else {
            //cout << ".,................................ " << endl;
            if (!nocares[v[j]]){
                amountOf[v[j]]++;
                if (amountOf[v[j]] >= needed[v[j]])fulfilled.insert(v[j]);
            }
            j++;
        }
 
        /*//cout << i << " " << j << endl;
        for (auto e : fulfilled)cout << e << endl;
        for (int i = 0; i < k; i++){
            if (!nocares[i])cout << i << ": " << amountOf[i] << ",  ";
        }
        cout << endl;*/
 
    }
 
    if (mini > 1e6)cout << "impossible" << endl;
    else cout << mini << endl;
 
 
 
    return 0;
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:58:40: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |         if (j == n || fulfilled.size() == r){
      |                       ~~~~~~~~~~~~~~~~~^~~~
dna.cpp:60:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |             if (fulfilled.size() == r) mini = min(mini, j-i);
      |                 ~~~~~~~~~~~~~~~~~^~~~

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