Submission #1078110

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1078110	2024-08-27T12:50:47 Z	Faisal_Saqib	Rarest Insects (IOI22_insects)	C++17	54.07 / 100	931 ms	37604 KB

insects

#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
				{
					add(j);
					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))
			// 		{
			// 			break;
			// 		}
			// 	}
			// }
		// }
		if(sm==((sz*mid)))
		{
			s=mid;
		}
		else{
			e=mid;
		}
	}
	return s;
}

Subtask #1

10.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	0 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	8 ms	568 KB	Output is correct
7	Correct	2 ms	344 KB	Output is correct
8	Correct	11 ms	600 KB	Output is correct
9	Correct	8 ms	760 KB	Output is correct
10	Correct	11 ms	836 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	7 ms	528 KB	Output is correct
13	Correct	6 ms	452 KB	Output is correct
14	Correct	7 ms	708 KB	Output is correct
15	Correct	7 ms	724 KB	Output is correct
16	Correct	8 ms	648 KB	Output is correct
17	Correct	7 ms	600 KB	Output is correct
18	Correct	7 ms	600 KB	Output is correct
19	Correct	6 ms	600 KB	Output is correct
20	Correct	4 ms	600 KB	Output is correct
21	Correct	3 ms	532 KB	Output is correct
22	Correct	2 ms	344 KB	Output is correct

Subtask #2

15.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	0 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	8 ms	568 KB	Output is correct
7	Correct	2 ms	344 KB	Output is correct
8	Correct	11 ms	600 KB	Output is correct
9	Correct	8 ms	760 KB	Output is correct
10	Correct	11 ms	836 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	7 ms	528 KB	Output is correct
13	Correct	6 ms	452 KB	Output is correct
14	Correct	7 ms	708 KB	Output is correct
15	Correct	7 ms	724 KB	Output is correct
16	Correct	8 ms	648 KB	Output is correct
17	Correct	7 ms	600 KB	Output is correct
18	Correct	7 ms	600 KB	Output is correct
19	Correct	6 ms	600 KB	Output is correct
20	Correct	4 ms	600 KB	Output is correct
21	Correct	3 ms	532 KB	Output is correct
22	Correct	2 ms	344 KB	Output is correct
23	Correct	159 ms	5448 KB	Output is correct
24	Correct	32 ms	2896 KB	Output is correct
25	Correct	114 ms	6372 KB	Output is correct
26	Correct	140 ms	8016 KB	Output is correct
27	Correct	72 ms	3132 KB	Output is correct
28	Correct	19 ms	1360 KB	Output is correct
29	Correct	93 ms	3756 KB	Output is correct
30	Correct	80 ms	4452 KB	Output is correct
31	Correct	162 ms	7664 KB	Output is correct
32	Correct	202 ms	8044 KB	Output is correct
33	Correct	169 ms	8932 KB	Output is correct
34	Correct	173 ms	8164 KB	Output is correct
35	Correct	180 ms	8472 KB	Output is correct
36	Correct	160 ms	8604 KB	Output is correct
37	Correct	115 ms	6992 KB	Output is correct
38	Correct	73 ms	4400 KB	Output is correct
39	Correct	58 ms	3532 KB	Output is correct
40	Correct	39 ms	2676 KB	Output is correct
41	Correct	26 ms	1908 KB	Output is correct

Subtask #3

29.07 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	690 ms	20832 KB	Output is correct
8	Correct	183 ms	10268 KB	Output is correct
9	Partially correct	684 ms	26812 KB	Output is partially correct
10	Partially correct	650 ms	29376 KB	Output is partially correct
11	Partially correct	238 ms	9748 KB	Output is partially correct
12	Correct	103 ms	6476 KB	Output is correct
13	Partially correct	297 ms	13504 KB	Output is partially correct
14	Partially correct	262 ms	14500 KB	Output is partially correct
15	Partially correct	787 ms	27240 KB	Output is partially correct
16	Partially correct	914 ms	30932 KB	Output is partially correct
17	Partially correct	837 ms	28500 KB	Output is partially correct
18	Partially correct	877 ms	31684 KB	Output is partially correct
19	Partially correct	931 ms	34656 KB	Output is partially correct
20	Partially correct	906 ms	33356 KB	Output is partially correct
21	Partially correct	710 ms	29820 KB	Output is partially correct
22	Partially correct	539 ms	26608 KB	Output is partially correct
23	Partially correct	242 ms	13836 KB	Output is partially correct
24	Correct	322 ms	13880 KB	Output is correct
25	Correct	204 ms	10320 KB	Output is correct
26	Correct	145 ms	7040 KB	Output is correct
27	Correct	501 ms	19760 KB	Output is correct
28	Partially correct	764 ms	37604 KB	Output is partially correct
29	Partially correct	612 ms	21644 KB	Output is partially correct
30	Partially correct	624 ms	22332 KB	Output is partially correct
31	Partially correct	560 ms	24064 KB	Output is partially correct
32	Partially correct	651 ms	28084 KB	Output is partially correct
33	Partially correct	300 ms	15264 KB	Output is partially correct
34	Partially correct	260 ms	14972 KB	Output is partially correct
35	Partially correct	594 ms	21336 KB	Output is partially correct
36	Partially correct	735 ms	28716 KB	Output is partially correct
37	Partially correct	560 ms	23900 KB	Output is partially correct
38	Partially correct	578 ms	23816 KB	Output is partially correct
39	Correct	438 ms	19560 KB	Output is correct
40	Partially correct	622 ms	31420 KB	Output is partially correct
41	Partially correct	768 ms	29236 KB	Output is partially correct
42	Partially correct	586 ms	22140 KB	Output is partially correct
43	Partially correct	37 ms	1264 KB	Output is partially correct
44	Partially correct	177 ms	6800 KB	Output is partially correct
45	Partially correct	748 ms	21048 KB	Output is partially correct
46	Correct	48 ms	2800 KB	Output is correct
47	Correct	227 ms	10828 KB	Output is correct
48	Correct	133 ms	6900 KB	Output is correct