| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 691024 | 2023-01-30T21:37:18 Z | CatalinT | Rarest Insects (IOI22_insects) | C++17 | 61 ms | 504 KB |
#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <sstream>
#include <queue>
#include "insects.h"
// void move_inside(int i);
// void move_outside(int i);
// int press_button();
using namespace std;
using int64 = long long;
int U;
int min_cardinality(int N) {
set<int> inside;
set<int> outside;
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() > 1) {
move_outside(i);
outside.insert(i);
} else {
inside.insert(i);
}
}
U = size(inside);
if (size(outside) < U) {
return 1;
}
// cerr << "U: " << U << " / " << size(outside) << "\n";
// binary search
int l = 2, r = N / U;
int sol = 1;
while (l <= r) {
int m = (l + r) >> 1;
// cerr << "try: " << m << "\n";
vector<int> first_half, second_half;
bool ok = false;
for (auto c : outside) {
// if ok then we can just add to second half
if (ok) {
second_half.push_back(c);
continue;
}
move_inside(c);
if (press_button() > m) {
// c is second half
move_outside(c);
second_half.push_back(c);
// cerr << c << " bad\n";
} else {
inside.insert(c);
// cerr << c << " good\n";
first_half.push_back(c);
if (size(inside) == m * U) {
// min frequency >= m
ok = true;
}
}
}
// cerr << "ok: " << ok << "\n";
if (ok) {
sol = m;
l = m + 1;
// go m + 1 ... r
// you don't need to remove anything
cerr << size(second_half) << " / " << size(first_half) << "\n";
outside = set<int>(begin(second_half), end(second_half));
} else {
// min frequency < m
// gol ... m - 1
r = m - 1;
// we need to remove every we added;
for (auto c : first_half) {
inside.erase(c);
move_outside(c);
}
assert(size(inside) % U == 0);
outside = set<int>(begin(first_half), end(first_half));
// cerr << "go lower: " << size(inside) << " / " << size(outside) << "\n";
}
}
return sol;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 208 KB | Output is correct |
| 2 | Correct | 0 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 | 5 ms | 208 KB | Output is correct |
| 7 | Correct | 2 ms | 208 KB | Output is correct |
| 8 | Correct | 5 ms | 300 KB | Output is correct |
| 9 | Correct | 3 ms | 312 KB | Output is correct |
| 10 | Correct | 7 ms | 208 KB | Output is correct |
| 11 | Correct | 2 ms | 208 KB | Output is correct |
| 12 | Correct | 4 ms | 208 KB | Output is correct |
| 13 | Correct | 4 ms | 208 KB | Output is correct |
| 14 | Correct | 3 ms | 208 KB | Output is correct |
| 15 | Correct | 4 ms | 300 KB | Output is correct |
| 16 | Correct | 6 ms | 208 KB | Output is correct |
| 17 | Correct | 8 ms | 300 KB | Output is correct |
| 18 | Correct | 5 ms | 316 KB | Output is correct |
| 19 | Correct | 3 ms | 208 KB | Output is correct |
| 20 | Correct | 4 ms | 208 KB | Output is correct |
| 21 | Correct | 3 ms | 208 KB | Output is correct |
| 22 | Correct | 2 ms | 208 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 208 KB | Output is correct |
| 2 | Correct | 0 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 | 5 ms | 208 KB | Output is correct |
| 7 | Correct | 2 ms | 208 KB | Output is correct |
| 8 | Correct | 5 ms | 300 KB | Output is correct |
| 9 | Correct | 3 ms | 312 KB | Output is correct |
| 10 | Correct | 7 ms | 208 KB | Output is correct |
| 11 | Correct | 2 ms | 208 KB | Output is correct |
| 12 | Correct | 4 ms | 208 KB | Output is correct |
| 13 | Correct | 4 ms | 208 KB | Output is correct |
| 14 | Correct | 3 ms | 208 KB | Output is correct |
| 15 | Correct | 4 ms | 300 KB | Output is correct |
| 16 | Correct | 6 ms | 208 KB | Output is correct |
| 17 | Correct | 8 ms | 300 KB | Output is correct |
| 18 | Correct | 5 ms | 316 KB | Output is correct |
| 19 | Correct | 3 ms | 208 KB | Output is correct |
| 20 | Correct | 4 ms | 208 KB | Output is correct |
| 21 | Correct | 3 ms | 208 KB | Output is correct |
| 22 | Correct | 2 ms | 208 KB | Output is correct |
| 23 | Correct | 12 ms | 336 KB | Output is correct |
| 24 | Correct | 9 ms | 312 KB | Output is correct |
| 25 | Correct | 22 ms | 336 KB | Output is correct |
| 26 | Correct | 24 ms | 360 KB | Output is correct |
| 27 | Correct | 20 ms | 328 KB | Output is correct |
| 28 | Correct | 9 ms | 336 KB | Output is correct |
| 29 | Correct | 17 ms | 324 KB | Output is correct |
| 30 | Correct | 28 ms | 332 KB | Output is correct |
| 31 | Correct | 17 ms | 336 KB | Output is correct |
| 32 | Correct | 25 ms | 328 KB | Output is correct |
| 33 | Correct | 26 ms | 312 KB | Output is correct |
| 34 | Correct | 26 ms | 324 KB | Output is correct |
| 35 | Correct | 23 ms | 336 KB | Output is correct |
| 36 | Correct | 25 ms | 320 KB | Output is correct |
| 37 | Correct | 27 ms | 324 KB | Output is correct |
| 38 | Correct | 15 ms | 336 KB | Output is correct |
| 39 | Correct | 17 ms | 328 KB | Output is correct |
| 40 | Correct | 15 ms | 320 KB | Output is correct |
| 41 | Correct | 10 ms | 316 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 208 KB | Output is correct |
| 2 | Correct | 0 ms | 208 KB | Output is correct |
| 3 | Correct | 1 ms | 208 KB | Output is correct |
| 4 | Correct | 0 ms | 208 KB | Output is correct |
| 5 | Correct | 1 ms | 208 KB | Output is correct |
| 6 | Correct | 1 ms | 208 KB | Output is correct |
| 7 | Correct | 40 ms | 480 KB | Output is correct |
| 8 | Correct | 18 ms | 368 KB | Output is correct |
| 9 | Correct | 49 ms | 436 KB | Output is correct |
| 10 | Correct | 37 ms | 452 KB | Output is correct |
| 11 | Correct | 38 ms | 464 KB | Output is correct |
| 12 | Correct | 28 ms | 376 KB | Output is correct |
| 13 | Correct | 50 ms | 436 KB | Output is correct |
| 14 | Correct | 56 ms | 332 KB | Output is correct |
| 15 | Correct | 38 ms | 504 KB | Output is correct |
| 16 | Correct | 49 ms | 360 KB | Output is correct |
| 17 | Correct | 49 ms | 452 KB | Output is correct |
| 18 | Correct | 31 ms | 476 KB | Output is correct |
| 19 | Correct | 33 ms | 424 KB | Output is correct |
| 20 | Correct | 38 ms | 432 KB | Output is correct |
| 21 | Correct | 55 ms | 464 KB | Output is correct |
| 22 | Correct | 50 ms | 348 KB | Output is correct |
| 23 | Correct | 43 ms | 312 KB | Output is correct |
| 24 | Correct | 31 ms | 404 KB | Output is correct |
| 25 | Correct | 22 ms | 336 KB | Output is correct |
| 26 | Correct | 19 ms | 320 KB | Output is correct |
| 27 | Correct | 51 ms | 456 KB | Output is correct |
| 28 | Correct | 37 ms | 356 KB | Output is correct |
| 29 | Correct | 48 ms | 464 KB | Output is correct |
| 30 | Correct | 31 ms | 448 KB | Output is correct |
| 31 | Correct | 61 ms | 428 KB | Output is correct |
| 32 | Correct | 42 ms | 344 KB | Output is correct |
| 33 | Correct | 44 ms | 344 KB | Output is correct |
| 34 | Correct | 41 ms | 496 KB | Output is correct |
| 35 | Partially correct | 54 ms | 488 KB | Output is partially correct |
| 36 | Correct | 31 ms | 408 KB | Output is correct |
| 37 | Correct | 43 ms | 424 KB | Output is correct |
| 38 | Correct | 56 ms | 456 KB | Output is correct |
| 39 | Correct | 42 ms | 436 KB | Output is correct |
| 40 | Correct | 40 ms | 416 KB | Output is correct |
| 41 | Correct | 40 ms | 460 KB | Output is correct |
| 42 | Partially correct | 50 ms | 360 KB | Output is partially correct |
| 43 | Correct | 14 ms | 208 KB | Output is correct |
| 44 | Correct | 22 ms | 328 KB | Output is correct |
| 45 | Correct | 19 ms | 456 KB | Output is correct |
| 46 | Correct | 20 ms | 372 KB | Output is correct |
| 47 | Correct | 29 ms | 308 KB | Output is correct |
| 48 | Correct | 21 ms | 356 KB | Output is correct |