#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+5;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl;
#define p2(x,y) cerr<<#x<<","<<#y<<" = "<<x<<" ,"<<y<<endl;
#else
#define p(x) {}
#define pv(x) {}
#define p2(x,y) {}
#endif
int min_cardinality(int n) {
int i,ret = 1;
vector<int> p1,p2,p3;
/// do some optimization
multiset<int> s;
int curr = 0;
//s.insert(0);
//move_inside(0);
bool in[n];
//p2(1,0)
int arr[n];
int j;
for(i=0;i<n;i++){
move_inside(i);
int x = press_button();
if(x == 1){
p1.push_back(i);
s.insert(curr);
curr++;
in[i] = true;
arr[i] = curr-1;
}
else{
//assert(x == 2);
p2.push_back(i);
move_outside(i);
}
}
int uni = p1.size();
int sq = sqrt(n);
if(uni >= 38){
while(1){
/// we have p1 with all the colors (uniquely)
vector<int> neo;
pv(p1)
pv(p2)
for(auto v : p2){
move_inside(v);
int x = press_button();
if(x == ret + 1){
neo.push_back(v);
}
else{
//assert(x == ret + 2);
p3.push_back(v);
move_outside(v);
}
}
p2 = neo;
pv(p2)
pv(p3)
/// we have p2 with all colors that have +1 occurence
//assert(p2.size() <= p1.size());
if(p2.size() < p1.size())return ret;
ret ++;
/// in the machine atm there are all of the colours 2 times each
p1 = p2;
p2 = p3;
p3.clear();
}
}
else{
/// we have small amount of unique colors
pv(p2)
random_shuffle(all(p2));
pv(p2)
for(auto i : p2){
move_inside(i);
in[i] = true;
//p2(1,i)
int x = press_button();
assert(x == 2);
bool ok =false;
p(i)
for(j=0;j<n;j++){
if(!in[j] || j == i)continue;
move_outside(j);
in[j] = false;
p2(2,j)
int x = press_button();
if(x == 1){
arr[i] = arr[j];
s.insert(arr[i]);
ok = true;
break;
}
p2(1,j)
move_inside(j);
in[j] = true;
}
//assert(ok);
}
int ret = n;
for(auto x : s){
ret = min(ret,(int)s.count(x));
}
return ret;
}
}
Compilation message
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:111:22: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
111 | bool ok =false;
| ^~
insects.cpp:60:9: warning: unused variable 'sq' [-Wunused-variable]
60 | int sq = sqrt(n);
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 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 |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
6 ms |
304 KB |
Output is correct |
| 7 |
Correct |
2 ms |
208 KB |
Output is correct |
| 8 |
Correct |
12 ms |
308 KB |
Output is correct |
| 9 |
Correct |
12 ms |
304 KB |
Output is correct |
| 10 |
Correct |
6 ms |
304 KB |
Output is correct |
| 11 |
Correct |
2 ms |
208 KB |
Output is correct |
| 12 |
Correct |
7 ms |
208 KB |
Output is correct |
| 13 |
Correct |
13 ms |
300 KB |
Output is correct |
| 14 |
Correct |
6 ms |
304 KB |
Output is correct |
| 15 |
Correct |
10 ms |
304 KB |
Output is correct |
| 16 |
Correct |
9 ms |
312 KB |
Output is correct |
| 17 |
Correct |
14 ms |
208 KB |
Output is correct |
| 18 |
Correct |
11 ms |
308 KB |
Output is correct |
| 19 |
Correct |
18 ms |
304 KB |
Output is correct |
| 20 |
Correct |
3 ms |
208 KB |
Output is correct |
| 21 |
Correct |
2 ms |
208 KB |
Output is correct |
| 22 |
Correct |
2 ms |
208 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 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 |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
0 ms |
208 KB |
Output is correct |
| 6 |
Correct |
6 ms |
304 KB |
Output is correct |
| 7 |
Correct |
2 ms |
208 KB |
Output is correct |
| 8 |
Correct |
12 ms |
308 KB |
Output is correct |
| 9 |
Correct |
12 ms |
304 KB |
Output is correct |
| 10 |
Correct |
6 ms |
304 KB |
Output is correct |
| 11 |
Correct |
2 ms |
208 KB |
Output is correct |
| 12 |
Correct |
7 ms |
208 KB |
Output is correct |
| 13 |
Correct |
13 ms |
300 KB |
Output is correct |
| 14 |
Correct |
6 ms |
304 KB |
Output is correct |
| 15 |
Correct |
10 ms |
304 KB |
Output is correct |
| 16 |
Correct |
9 ms |
312 KB |
Output is correct |
| 17 |
Correct |
14 ms |
208 KB |
Output is correct |
| 18 |
Correct |
11 ms |
308 KB |
Output is correct |
| 19 |
Correct |
18 ms |
304 KB |
Output is correct |
| 20 |
Correct |
3 ms |
208 KB |
Output is correct |
| 21 |
Correct |
2 ms |
208 KB |
Output is correct |
| 22 |
Correct |
2 ms |
208 KB |
Output is correct |
| 23 |
Correct |
30 ms |
300 KB |
Output is correct |
| 24 |
Correct |
7 ms |
336 KB |
Output is correct |
| 25 |
Correct |
110 ms |
448 KB |
Output is correct |
| 26 |
Correct |
99 ms |
320 KB |
Output is correct |
| 27 |
Correct |
28 ms |
324 KB |
Output is correct |
| 28 |
Correct |
8 ms |
328 KB |
Output is correct |
| 29 |
Correct |
24 ms |
436 KB |
Output is correct |
| 30 |
Correct |
107 ms |
332 KB |
Output is correct |
| 31 |
Runtime error |
8 ms |
428 KB |
Execution killed with signal 6 |
| 32 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
0 ms |
208 KB |
Output is correct |
| 6 |
Partially correct |
1 ms |
208 KB |
Output is partially correct |
| 7 |
Runtime error |
14 ms |
560 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
