#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()/3 > 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 == 1) {
// cout << outside2 << nL;
// }
bool res = false;
int curr = press_button();
for (int i = 0; i < 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() > N/2) return 1;
int maxN = (N-first.size())+1;
int lo = 1, hi = maxN, 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:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < first.size() && !res; i++) {
| ~~^~~~~~~~~~~~~~
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: 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:113:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
113 | if (first.size() > N/2) return 1;
| ~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
600 KB |
Wrong answer. |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
5 ms |
600 KB |
Wrong answer. |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Partially correct |
0 ms |
592 KB |
Output is partially correct |
| 6 |
Partially correct |
1 ms |
344 KB |
Output is partially correct |
| 7 |
Incorrect |
46 ms |
668 KB |
Wrong answer. |
| 8 |
Halted |
0 ms |
0 KB |
- |
