#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
set<int> machine,rem;
int sm=0;
void add(int x)
{
if(machine.find(x)==machine.end())
{
move_inside(x);
machine.insert(x);
sm++;
}
}
void remp(int x)
{
if(machine.find(x)!=machine.end())
{
move_outside(x);
machine.erase(x);
sm--;
}
}
map<vector<int>,int> store;
int ask()
{
vector<int> cur(begin(machine),end(machine));
if(store.find(cur)==store.end())
store[cur]=press_button();
// cout<<"Query for: ";
// for(auto j:cur)
// {
// cout<<j<<' ';
// }
// cout<<" ans: "<<store[cur]<<endl;
return store[cur];
}
int min_cardinality(int n)
{
add(0);
for(int i=1;i<n;i++)
{
add(i);
if(ask()>1)
{
rem.insert(i);
remp(i);
}
}
int sz=sm;
int s=1;
int e=(n/sz)+1;
while(s+1<e)
{
int mid=(s+e)/2;
vector<int> cur;
// cout<<endl;
// cout<<"for "<<mid<<endl;
// cout<<"\nMachine: ";
// for(auto j:machine)
// {
// cout<<j<<' ';
// }
// cout<<endl;
for(auto i:rem)
{
// cout<<"Add and query "<<i<<endl;
add(i);
if(ask()>mid)
{
remp(i);
}
else
{
sm++;
cur.push_back(i);
if(sm==(sz*mid))
break;
}
}
if(sm==((sz*mid)))
{
s=mid;
// We can make values in amachin so keep
for(auto i:cur)
rem.erase(i);
}
else{
e=mid;
sm=0;
rem.clear();
for(auto i:machine)
rem.insert(i);
for(auto i:rem)
remp(i);
}
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Wrong answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Wrong answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Wrong answer. |
| 3 |
Halted |
0 ms |
0 KB |
- |
