#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
map<set<int>,int> store;
set<int> cur,real_;
void add(int i)
{
i--;
cur.insert(i);
}
void rem(int i)
{
i--;
if(cur.find(i)!=cur.end())
cur.erase(i);
}
void khatam()
{
cur.clear();
}
int ask()
{
if(store.find(cur)!=store.end())return store[cur];
for(auto i:cur)
{
if(real_.find(i)==real_.end())
{
real_.insert(i);
move_inside(i);
}
}
set<int> rem;
for(auto j:real_)
{
if(cur.find(j)==cur.end())
{
rem.insert(j);
move_outside(j);
}
}
for(auto i:rem)real_.erase(i);
return store[cur]=press_button();
}
const int M=2e3+10;
int par[M],sz[M];
int get(int x)
{
if(par[x]==x)return x;
return par[x]=get(par[x]);
}
void merge(int x,int y)
{
x=get(x);
y=get(y);
par[y]=x;
sz[x]+=sz[y];
}
int min_cardinality(int n)
{
for(int i=1;i<=n;i++)
par[i]=i,sz[i]=1;
vector<int> heads={1};
for(int i=2;i<=n;i++)
{
int sz=heads.size();
int s=0,e=sz;
// can be head[s]
// not head[e]
while(s+1<e)
{
int mid=(s+e)/2;
khatam();
for(int j=s;j<=mid;j++)
add(heads[j]);
add(i);
int aft=ask();
if(aft==2)
{
e=mid;
}
else
{
s=mid;
}
}
if(e==sz)
{
heads.push_back(i);
}
else
{
merge(heads[e],i);
}
}
int mi=n+1;
for(auto i:heads)
mi=min(mi,sz[i]);
return mi;
}
| # |
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 |
1 ms |
344 KB |
Wrong answer. |
| 3 |
Halted |
0 ms |
0 KB |
- |
