| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 689959 |
2023-01-29T21:53:07 Z |
NK_ |
Martian DNA (BOI18_dna) |
C++17 |
|
115 ms |
19956 KB |
// 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(K, -1);
for(int i = 0; i < R; i++) {
int x, y; cin >> x >> y; Q[x] = --y;
}
set<int> S;
for(int i = 0; i < K; i++) {
if (Q[i] == -1) continue;
if (Q[i] >= int(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(oc[x][Q[x]]);
++Q[x];
if (Q[x] >= int(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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
320 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2420 KB |
Output is correct |
| 2 |
Correct |
17 ms |
2328 KB |
Output is correct |
| 3 |
Correct |
22 ms |
2144 KB |
Output is correct |
| 4 |
Correct |
18 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
44 ms |
9628 KB |
Output is correct |
| 6 |
Correct |
12 ms |
2260 KB |
Output is correct |
| 7 |
Correct |
12 ms |
2132 KB |
Output is correct |
| 8 |
Correct |
66 ms |
17788 KB |
Output is correct |
| 9 |
Correct |
56 ms |
2932 KB |
Output is correct |
| 10 |
Correct |
21 ms |
2168 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
468 KB |
Output is correct |
| 14 |
Correct |
1 ms |
596 KB |
Output is correct |
| 15 |
Correct |
1 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
212 KB |
Output is correct |
| 23 |
Correct |
0 ms |
212 KB |
Output is correct |
| 24 |
Correct |
0 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
9428 KB |
Output is correct |
| 2 |
Correct |
79 ms |
7508 KB |
Output is correct |
| 3 |
Correct |
63 ms |
7460 KB |
Output is correct |
| 4 |
Correct |
20 ms |
2288 KB |
Output is correct |
| 5 |
Correct |
50 ms |
7024 KB |
Output is correct |
| 6 |
Correct |
115 ms |
19956 KB |
Output is correct |
| 7 |
Correct |
25 ms |
2908 KB |
Output is correct |
| 8 |
Correct |
59 ms |
4048 KB |
Output is correct |
| 9 |
Correct |
16 ms |
2356 KB |
Output is correct |
| 10 |
Correct |
17 ms |
2328 KB |
Output is correct |
| 11 |
Correct |
22 ms |
2132 KB |
Output is correct |
| 12 |
Correct |
19 ms |
2400 KB |
Output is correct |
| 13 |
Correct |
47 ms |
9564 KB |
Output is correct |
| 14 |
Correct |
11 ms |
2260 KB |
Output is correct |
| 15 |
Correct |
15 ms |
2132 KB |
Output is correct |
| 16 |
Correct |
83 ms |
17764 KB |
Output is correct |
| 17 |
Correct |
54 ms |
2900 KB |
Output is correct |
| 18 |
Correct |
21 ms |
2260 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
468 KB |
Output is correct |
| 22 |
Correct |
1 ms |
596 KB |
Output is correct |
| 23 |
Correct |
2 ms |
468 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
0 ms |
212 KB |
Output is correct |
| 28 |
Correct |
0 ms |
212 KB |
Output is correct |
| 29 |
Correct |
0 ms |
212 KB |
Output is correct |
| 30 |
Correct |
1 ms |
212 KB |
Output is correct |
| 31 |
Correct |
0 ms |
212 KB |
Output is correct |
| 32 |
Correct |
0 ms |
212 KB |
Output is correct |
| 33 |
Correct |
1 ms |
212 KB |
Output is correct |
