oj.uz

Submission #1078179

# Submission time Handle Problem Language Result Execution time Memory
1078179 2024-08-27T13:36:22 Z Faisal_Saqib Rarest Insects (IOI22_insects) C++17
0 / 100
 2000 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;
set<int> cur,machine;
void add(int&i)
{
	cur.insert(i-1);
}
void rem(int&i)
{
	cur.erase(i-1);
}
void khatam()
{
	cur.clear();
}
int ask()
{
	vector<int> vec(begin(cur),end(cur));
	if(store.find(vec)!=store.end())return store[vec];
	for(auto&i:cur)
		if(machine.find(i)==machine.end())
			move_inside(i);
	for(auto&j:machine)
		if(cur.find(j)==cur.end())
			move_outside(j);
	machine=cur;
	store[vec]=press_button();
	return store[vec];
}
int min_cardinality(int n)
{
	vector<int> heads={1};
	int one=1;
	add(one);
	for(int i=2;i<=n;i++)
	{
		add(i);
		if(ask()==1)
			heads.push_back(i);
		else
			rem(i);
	}
	int sz=heads.size(),np=n;
	int sm=0;
	while(1)
	{
		int mid=(np)/sz;
		khatam();
		for(int i=1;i<=n and sm<(sz*mid);i++)
		{
			if(i<=mid)
			{
				add(i);
				sm++;
			}
			else
			{				
				add(i);
				if(ask()>mid)
				{
					rem(i);
				}
				else
				{
					sm++;
				}
			}
		}
		if(sm==((sz*mid)))
		{
			return mid; // this is the answer
		}
		else{
			np=sm;
		}
	}
	return -1;
}

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 Execution timed out 3037 ms 344 KB Time limit exceeded
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 Execution timed out 3037 ms 344 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -