Submission #1077368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077368		Faisal_Saqib	Rarest Insects (IOI22_insects)	C++17	10 / 100	2041 ms	94940 KiB

insects

#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);
	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];
}
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++)
	{
		khatam();
		for(auto p:heads)add(p);
		add(i);
		if(ask()==2)
		{
			int sz=heads.size();
			int s=-1,e=sz;
			// can be head[s] 
			// not head[e]
			while(s+1<e)
			{
				int mid=(s+e)/2;
				khatam();
				for(int j=s+1;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);
			}
		}
		else
		{
			heads.push_back(i);
		}
	}
	int mi=n+1;
	for(auto i:heads)
		mi=min(mi,sz[i]);
	return mi;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75