oj.uz

Submission #1078094

# Submission time Handle Problem Language Result Execution time Memory
1078094 2024-08-27T12:38:59 Z Faisal_Saqib Rarest Insects (IOI22_insects) C++17
0 / 100
 1 ms 344 KB 
#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(begin(real_),end(real_),i))
		{
			move_inside(i);
		}
	}
	for(auto&j:real_)
	{
		if(!binary_search(begin(cur),end(cur),j))
		{
			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/sz)+1;
	while(s+1<e)
	{
		int mid=(s+e)/2;
		khatam();
		int sm=0;
		if(sz>=mid)
		{
			for(int i=0;i<sz;i++)
				add(heads[i]),sm++;
			for(int j=1;j<=n;j++)
			{
				if(!binary_search(begin(heads),end(heads),j))
				{					
					add(j);
					if(ask()>mid)
					{
						rem(j);
					}
					else{
						sm++;
					}
				}
			}
		}
		else
		{
			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;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB Wrong answer.
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB Wrong answer.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Incorrect 1 ms 344 KB Wrong answer.
6 Halted 0 ms 0 KB -