Submission #689955

#	Time	Username	Problem	Language	Result	Execution time	Memory
689955		NK_	Martian DNA (BOI18_dna)	C++17	0 / 100	66 ms	20880 KiB

dna

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K, R; cin >> N >> K >> R;

	vector<int> A(N); for(auto& x : A) cin >> x;

	vector<vector<int>> oc(K); for(int i = 0; i < N; i++) oc[A[i]].push_back(i);
	
	vector<int> Q(R, -1); 
	for(int i = 0; i < R; i++) {
		int x, y; cin >> x >> y; Q[x] = --y;
	}

	multiset<int> S; 
	for(int i = 0; i < K; i++) {
		if (Q[i] == -1) continue;
		if (Q[i] >= size(oc[i])) {
			cout << "impossible" << nl;
			return 0;
		}
		S.insert(oc[i][Q[i]]);
	}

	int ans = N + 1;
	for(int l = 0; l < N; l++) {
		int x = A[l];

		int r = *rbegin(S);
		ans = min(ans, r - l + 1);

		S.erase(S.find(oc[x][Q[x]]));
		if ((++Q[x]) >= size(oc[x])) break;
		S.insert(oc[x][Q[x]]);
	}

	cout << ans << nl;

    return 0;
}

/*
13 4 3 
1 1 3 2 0 1 2 0 0 0 0 3 1  
0 2
2 1
1 2

5 3 1 
1 2 0 1 2  
0 2

*/

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:25:12: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   if (Q[i] >= size(oc[i])) {
dna.cpp:40:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   if ((++Q[x]) >= size(oc[x])) break;
      |       ~~~~~~~~~^~~~~~~~~~~~~~

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