#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(uni == 40 && 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 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
