// correct/solution-prabowo-ac.cpp
#include "insects.h"
#include <map>
#include <numeric>
#include <vector>
int N;
std::vector<bool> lastPress, where;
void _move_inside(int i) {
where[i] = true;
}
void _move_outside(int i) {
where[i] = false;
}
std::map<std::vector<bool>, int> memo;
int _press_button() {
if (memo.find(where) != memo.end()) return memo[where];
for (int i = 0; i < N; ++i) {
if (where[i] == lastPress[i]) continue;
if (where[i]) move_inside(i);
else move_outside(i);
}
lastPress = where;
return memo[where] = press_button();
}
int min_cardinality(int _N) {
N = _N;
lastPress.assign(N, false); where.assign(N, false);
std::vector<int> insects(N);
std::iota(insects.begin(), insects.end(), 0);
std::vector<bool> isInside(N);
// Count distincts
std::vector<int> insides, outsides;
int inside = 0;
for (int insect : insects) {
_move_inside(insect);
if (_press_button() > 1) {
_move_outside(insect);
outsides.push_back(insect);
} else {
insides.push_back(insect);
++inside;
}
}
int distinct = inside;
insects = outsides;
int l = 1, r = N / distinct;
int ans = -1;
while (l <= r) {
int mid = (l + r + 1) / 2;
insides.clear(); outsides.clear();
for (int insect : insects) {
_move_inside(insect);
if (_press_button() > mid) {
_move_outside(insect);
outsides.push_back(insect);
} else {
insides.push_back(insect);
++inside;
}
}
if (inside == mid * distinct) {
ans = mid;
l = mid + 1;
insects = outsides;
} else {
r = mid - 1;
insects = insides;
for (int insect : insects) {
_move_outside(insect);
--inside;
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
1 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
12 ms |
336 KB |
Output is correct |
7 |
Correct |
2 ms |
208 KB |
Output is correct |
8 |
Correct |
15 ms |
348 KB |
Output is correct |
9 |
Correct |
10 ms |
336 KB |
Output is correct |
10 |
Correct |
5 ms |
296 KB |
Output is correct |
11 |
Correct |
4 ms |
308 KB |
Output is correct |
12 |
Correct |
7 ms |
340 KB |
Output is correct |
13 |
Correct |
12 ms |
336 KB |
Output is correct |
14 |
Correct |
9 ms |
348 KB |
Output is correct |
15 |
Correct |
12 ms |
348 KB |
Output is correct |
16 |
Correct |
11 ms |
340 KB |
Output is correct |
17 |
Correct |
8 ms |
384 KB |
Output is correct |
18 |
Correct |
6 ms |
352 KB |
Output is correct |
19 |
Correct |
8 ms |
356 KB |
Output is correct |
20 |
Correct |
9 ms |
436 KB |
Output is correct |
21 |
Correct |
15 ms |
208 KB |
Output is correct |
22 |
Correct |
3 ms |
316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
1 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
12 ms |
336 KB |
Output is correct |
7 |
Correct |
2 ms |
208 KB |
Output is correct |
8 |
Correct |
15 ms |
348 KB |
Output is correct |
9 |
Correct |
10 ms |
336 KB |
Output is correct |
10 |
Correct |
5 ms |
296 KB |
Output is correct |
11 |
Correct |
4 ms |
308 KB |
Output is correct |
12 |
Correct |
7 ms |
340 KB |
Output is correct |
13 |
Correct |
12 ms |
336 KB |
Output is correct |
14 |
Correct |
9 ms |
348 KB |
Output is correct |
15 |
Correct |
12 ms |
348 KB |
Output is correct |
16 |
Correct |
11 ms |
340 KB |
Output is correct |
17 |
Correct |
8 ms |
384 KB |
Output is correct |
18 |
Correct |
6 ms |
352 KB |
Output is correct |
19 |
Correct |
8 ms |
356 KB |
Output is correct |
20 |
Correct |
9 ms |
436 KB |
Output is correct |
21 |
Correct |
15 ms |
208 KB |
Output is correct |
22 |
Correct |
3 ms |
316 KB |
Output is correct |
23 |
Correct |
160 ms |
852 KB |
Output is correct |
24 |
Correct |
38 ms |
488 KB |
Output is correct |
25 |
Correct |
125 ms |
936 KB |
Output is correct |
26 |
Correct |
131 ms |
828 KB |
Output is correct |
27 |
Correct |
89 ms |
704 KB |
Output is correct |
28 |
Correct |
60 ms |
536 KB |
Output is correct |
29 |
Correct |
99 ms |
784 KB |
Output is correct |
30 |
Correct |
124 ms |
904 KB |
Output is correct |
31 |
Correct |
147 ms |
1092 KB |
Output is correct |
32 |
Correct |
147 ms |
844 KB |
Output is correct |
33 |
Correct |
142 ms |
908 KB |
Output is correct |
34 |
Correct |
168 ms |
836 KB |
Output is correct |
35 |
Correct |
128 ms |
920 KB |
Output is correct |
36 |
Correct |
138 ms |
892 KB |
Output is correct |
37 |
Correct |
138 ms |
848 KB |
Output is correct |
38 |
Correct |
103 ms |
892 KB |
Output is correct |
39 |
Correct |
119 ms |
1044 KB |
Output is correct |
40 |
Correct |
87 ms |
672 KB |
Output is correct |
41 |
Correct |
56 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
228 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
1 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
1 ms |
208 KB |
Output is correct |
7 |
Correct |
594 ms |
2436 KB |
Output is correct |
8 |
Correct |
184 ms |
892 KB |
Output is correct |
9 |
Correct |
501 ms |
2320 KB |
Output is correct |
10 |
Correct |
636 ms |
2348 KB |
Output is correct |
11 |
Correct |
313 ms |
1788 KB |
Output is correct |
12 |
Correct |
273 ms |
1248 KB |
Output is correct |
13 |
Correct |
373 ms |
2068 KB |
Output is correct |
14 |
Correct |
389 ms |
2236 KB |
Output is correct |
15 |
Correct |
623 ms |
2384 KB |
Output is correct |
16 |
Correct |
617 ms |
2376 KB |
Output is correct |
17 |
Correct |
535 ms |
2392 KB |
Output is correct |
18 |
Correct |
508 ms |
2392 KB |
Output is correct |
19 |
Correct |
497 ms |
2388 KB |
Output is correct |
20 |
Correct |
546 ms |
2356 KB |
Output is correct |
21 |
Correct |
479 ms |
2508 KB |
Output is correct |
22 |
Correct |
491 ms |
2160 KB |
Output is correct |
23 |
Correct |
360 ms |
2140 KB |
Output is correct |
24 |
Correct |
398 ms |
2064 KB |
Output is correct |
25 |
Correct |
271 ms |
1552 KB |
Output is correct |
26 |
Correct |
212 ms |
1240 KB |
Output is correct |
27 |
Correct |
448 ms |
2208 KB |
Output is correct |
28 |
Correct |
489 ms |
2244 KB |
Output is correct |
29 |
Correct |
605 ms |
2304 KB |
Output is correct |
30 |
Correct |
541 ms |
2236 KB |
Output is correct |
31 |
Correct |
463 ms |
2104 KB |
Output is correct |
32 |
Correct |
489 ms |
2292 KB |
Output is correct |
33 |
Correct |
374 ms |
1976 KB |
Output is correct |
34 |
Correct |
493 ms |
1852 KB |
Output is correct |
35 |
Correct |
540 ms |
2224 KB |
Output is correct |
36 |
Correct |
689 ms |
2232 KB |
Output is correct |
37 |
Correct |
483 ms |
2148 KB |
Output is correct |
38 |
Correct |
550 ms |
2104 KB |
Output is correct |
39 |
Correct |
536 ms |
2256 KB |
Output is correct |
40 |
Correct |
442 ms |
2160 KB |
Output is correct |
41 |
Correct |
493 ms |
2324 KB |
Output is correct |
42 |
Correct |
498 ms |
2260 KB |
Output is correct |
43 |
Correct |
41 ms |
404 KB |
Output is correct |
44 |
Correct |
338 ms |
1600 KB |
Output is correct |
45 |
Correct |
617 ms |
2516 KB |
Output is correct |
46 |
Correct |
210 ms |
1360 KB |
Output is correct |
47 |
Correct |
247 ms |
1304 KB |
Output is correct |
48 |
Correct |
250 ms |
1276 KB |
Output is correct |