#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);
in[i] = false;
}
}
int uni = p1.size();
int sq = sqrt(n);
assert(n != 2000);
if(uni >= 55){
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:112:22: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
112 | bool ok =false;
| ^~
insects.cpp:61:9: warning: unused variable 'sq' [-Wunused-variable]
61 | int sq = sqrt(n);
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
4 ms |
208 KB |
Output is correct |
7 |
Correct |
1 ms |
208 KB |
Output is correct |
8 |
Correct |
13 ms |
288 KB |
Output is correct |
9 |
Correct |
15 ms |
308 KB |
Output is correct |
10 |
Correct |
5 ms |
296 KB |
Output is correct |
11 |
Correct |
3 ms |
208 KB |
Output is correct |
12 |
Correct |
5 ms |
208 KB |
Output is correct |
13 |
Correct |
15 ms |
208 KB |
Output is correct |
14 |
Correct |
7 ms |
308 KB |
Output is correct |
15 |
Correct |
6 ms |
208 KB |
Output is correct |
16 |
Correct |
9 ms |
208 KB |
Output is correct |
17 |
Correct |
12 ms |
284 KB |
Output is correct |
18 |
Correct |
14 ms |
208 KB |
Output is correct |
19 |
Correct |
17 ms |
312 KB |
Output is correct |
20 |
Correct |
22 ms |
300 KB |
Output is correct |
21 |
Correct |
3 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 |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
4 ms |
208 KB |
Output is correct |
7 |
Correct |
1 ms |
208 KB |
Output is correct |
8 |
Correct |
13 ms |
288 KB |
Output is correct |
9 |
Correct |
15 ms |
308 KB |
Output is correct |
10 |
Correct |
5 ms |
296 KB |
Output is correct |
11 |
Correct |
3 ms |
208 KB |
Output is correct |
12 |
Correct |
5 ms |
208 KB |
Output is correct |
13 |
Correct |
15 ms |
208 KB |
Output is correct |
14 |
Correct |
7 ms |
308 KB |
Output is correct |
15 |
Correct |
6 ms |
208 KB |
Output is correct |
16 |
Correct |
9 ms |
208 KB |
Output is correct |
17 |
Correct |
12 ms |
284 KB |
Output is correct |
18 |
Correct |
14 ms |
208 KB |
Output is correct |
19 |
Correct |
17 ms |
312 KB |
Output is correct |
20 |
Correct |
22 ms |
300 KB |
Output is correct |
21 |
Correct |
3 ms |
208 KB |
Output is correct |
22 |
Correct |
2 ms |
208 KB |
Output is correct |
23 |
Correct |
15 ms |
312 KB |
Output is correct |
24 |
Correct |
7 ms |
344 KB |
Output is correct |
25 |
Correct |
93 ms |
456 KB |
Output is correct |
26 |
Correct |
130 ms |
308 KB |
Output is correct |
27 |
Correct |
22 ms |
304 KB |
Output is correct |
28 |
Correct |
16 ms |
348 KB |
Output is correct |
29 |
Correct |
30 ms |
332 KB |
Output is correct |
30 |
Correct |
132 ms |
304 KB |
Output is correct |
31 |
Correct |
28 ms |
308 KB |
Output is correct |
32 |
Correct |
48 ms |
304 KB |
Output is correct |
33 |
Correct |
42 ms |
328 KB |
Output is correct |
34 |
Correct |
47 ms |
308 KB |
Output is correct |
35 |
Correct |
72 ms |
312 KB |
Output is correct |
36 |
Correct |
84 ms |
328 KB |
Output is correct |
37 |
Correct |
152 ms |
312 KB |
Output is correct |
38 |
Correct |
22 ms |
308 KB |
Output is correct |
39 |
Correct |
11 ms |
316 KB |
Output is correct |
40 |
Correct |
17 ms |
316 KB |
Output is correct |
41 |
Correct |
10 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
0 ms |
208 KB |
Output is correct |
7 |
Runtime error |
12 ms |
432 KB |
Execution killed with signal 6 |
8 |
Halted |
0 ms |
0 KB |
- |