#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 2e3 + 10;
const int lg = 20;
int l[maxn], r[maxn], cnt[maxn];
vector<int> a, b;
vector<int> idx[maxn];
bool check_empty(int x){
for (int i = x; i < a.size(); i++){
if (!idx[i].empty()) return false;
}
return true;
}
int min_cardinality(int N) {
int n = N;
vector<int> A;
for (int i = 0; i < n; i++) A.push_back(i);
for (auto i: A){
move_inside(i);
if (press_button() == 2){
move_outside(i);
b.push_back(i);
continue;
}
a.push_back(i);
}
for (int i = 0; i < a.size(); i++){
move_outside(i);
}
for (int i = 0; i < b.size(); i++){
l[i] = -1, r[i] = a.size() - 1;
if (l[i] + 1 < r[i]){
int mid = (l[i] + r[i]) >> 1;
idx[mid].push_back(i);
}
}
//debug(a.size(), b.size());
for (int i = 0; i < lg; i++){
if (check_empty(0)) break;
for (int j = 0; j < a.size(); j++){
move_inside(a[j]);
for (auto x: idx[j]){
move_inside(b[x]);
if (press_button() == j) r[x] = j;
else l[x] = j;
if (l[x] + 1 < r[x]){
int mid = (l[x] + r[x]) >> 1;
idx[mid].push_back(x);
}
move_outside(b[x]);
}
idx[j].clear();
}
for (int j = 0; j < a.size(); j++){
move_outside(a[j]);
}
}
for (int i = 0; i < b.size(); i++){
cnt[r[i]]++;
}
int ans = n;
for (int i = 0; i < a.size(); i++){
ans = min(ans, cnt[i]);
// debug(cnt[i]);
}
return ans+1;
}
Compilation message
insects.cpp: In function 'bool check_empty(int)':
insects.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = x; i < a.size(); i++){
| ~~^~~~~~~~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 0; i < a.size(); i++){
| ~~^~~~~~~~~~
insects.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0; i < b.size(); i++){
| ~~^~~~~~~~~~
insects.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int j = 0; j < a.size(); j++){
| ~~^~~~~~~~~~
insects.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int j = 0; j < a.size(); j++){
| ~~^~~~~~~~~~
insects.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int i = 0; i < b.size(); i++){
| ~~^~~~~~~~~~
insects.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i < a.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
336 KB |
Wrong answer. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
336 KB |
Wrong answer. |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
336 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
0 ms |
336 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
336 KB |
Wrong answer. |
| 7 |
Halted |
0 ms |
0 KB |
- |
