#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
const ll MOD = 1e9 + 7;
void settings()__attribute__((constructor));
int ipow(int a, int n) {
if (n == 0) return 1;
int x = ipow(a, n/2);
if (n % 2 == 0) return x*x;
return x*x*a;
}
template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
for (auto elem : v)
stream << elem << " ";
return stream;
}
template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
for(auto &elem : v)
stream >> elem;
return stream;
}
vi first;
bool check(int N, int rarity) {
vi inside, outside;
for (int i = 0; i < N; i++) {
move_inside(i);
if (i >= rarity && press_button() > rarity) {
move_outside(i);
outside.pb(i);
} else {
inside.pb(i);
}
}
for (int i = 0; i < inside.size(); i++) move_outside(inside[i]);
if (inside.size() % rarity != 0) return true;
if (inside.size()/rarity > outside.size()) return true;
// if (rarity == 1) {
// cout << outside << nL;
// }
vi outside2;
for (int i = 0; i < outside.size(); i++) {
move_inside(outside[i]);
if (press_button() == 1) {
outside2.pb(outside[i]);
} else {
move_outside(outside[i]);
}
}
// if (rarity == 6) {
// cout << outside2 << nL;
// }
bool res = false;
int curr = press_button();
for (int i = first.size()-1; i >= 0 first.size() && !res; i--) {
move_inside(first[i]);
if (press_button() == curr) {
res = true;
}
move_outside(first[i]);
}
for (int i = 0; i < outside2.size(); i++) move_outside(outside2[i]);
return res;
}
int min_cardinality(int N) {
first = vi();
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() == 1) {
first.pb(i);
} else {
move_outside(i);
}
}
for (int i = 0; i < first.size(); i++) move_outside(first[i]);
if (first.size() == 1) return N;
if (first.size() > N/2) return 1;
int maxN = (N-first.size())/first.size()+1;
int lo = 1, hi = maxN-1, res = maxN, mid;
while (lo <= hi) {
mid = (lo+hi)/2;
if (check(N, mid)) {
res = mid;
hi = mid - 1;
} else
lo = mid + 1;
}
return res;
}
Compilation message
insects.cpp: In function 'bool check(int, int)':
insects.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i < inside.size(); i++) move_outside(inside[i]);
| ~~^~~~~~~~~~~~~~~
insects.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < outside.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
insects.cpp:88:38: error: expected ';' before 'first'
88 | for (int i = first.size()-1; i >= 0 first.size() && !res; i--) {
| ^~~~~~
| ;
insects.cpp:88:59: error: expected ')' before ';' token
88 | for (int i = first.size()-1; i >= 0 first.size() && !res; i--) {
| ~ ^
| )
insects.cpp:88:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
88 | for (int i = first.size()-1; i >= 0 first.size() && !res; i--) {
| ^~~
insects.cpp:88:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
88 | for (int i = first.size()-1; i >= 0 first.size() && !res; i--) {
| ^
insects.cpp:88:61: error: 'i' was not declared in this scope
insects.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int i = 0; i < outside2.size(); i++) move_outside(outside2[i]);
| ~~^~~~~~~~~~~~~~~~~
insects.cpp:87:7: warning: unused variable 'curr' [-Wunused-variable]
87 | int curr = press_button();
| ^~~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:111:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < first.size(); i++) move_outside(first[i]);
| ~~^~~~~~~~~~~~~~
insects.cpp:114:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | if (first.size() > N/2) return 1;
| ~~~~~~~~~~~~~^~~~~
