| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1078086 | Faisal_Saqib | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
map<vector<int>,int> store;
vector<int> cur,real_;
void add(int i)
{
i--;
cur.push_back(i);
}
void rem(int i)
{
i--;
cur.pop_back();
}
void khatam()
{
cur.clear();
}
int ask()
{
if(store.find(cur)!=store.end())return store[cur];
for(auto&i:cur)
{
if(!binary_search(all(real),i))
{
move_inside(i);
}
}
for(auto&j:real_)
{
if(!binary_search(all(cur),i))
{
move_outside(j);
}
}
real_=cur;
store[cur]=press_button();
// cout<<"asking \n";
// cout<<"For: ";
// for(auto i:cur)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// cout<<"Ans: "<<store[cur]<<endl;
return store[cur];
}
int min_cardinality(int n)
{
vector<int> heads={1};
add(1);
for(int i=2;i<=n;i++)
{
add(i);
if(ask()==1)
heads.push_back(i);
else
rem(i);
}
int sz=heads.size();
int s=1;
int e=n+1;
while(s+1<e)
{
int mid=(s+e)/2;
khatam();
int sm=0;
for(int i=1;i<=mid;i++)
add(i),sm++;
for(int j=mid+1;j<=n;j++)
{
add(j);
if(ask()>mid)
{
rem(j);
}
else{
sm++;
}
}
if(sm==((sz*mid)))
{
s=mid;
}
else{
e=mid;
}
}
return s;
}