oj.uz

Submission #1078099

# Submission time Handle Problem Language Result Execution time Memory
1078099 2024-08-27T12:43:21 Z Faisal_Saqib Rarest Insects (IOI22_insects) C++17
54.05 / 100
 897 ms 29500 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))
					{
						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 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 4 ms 536 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 8 ms 600 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 13 ms 600 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 11 ms 572 KB Output is correct
13 Correct 10 ms 600 KB Output is correct
14 Correct 6 ms 600 KB Output is correct
15 Correct 7 ms 856 KB Output is correct
16 Correct 10 ms 600 KB Output is correct
17 Correct 8 ms 856 KB Output is correct
18 Correct 6 ms 600 KB Output is correct
19 Correct 6 ms 600 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 4 ms 344 KB Output is correct
22 Correct 4 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 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 4 ms 536 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 8 ms 600 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 13 ms 600 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 11 ms 572 KB Output is correct
13 Correct 10 ms 600 KB Output is correct
14 Correct 6 ms 600 KB Output is correct
15 Correct 7 ms 856 KB Output is correct
16 Correct 10 ms 600 KB Output is correct
17 Correct 8 ms 856 KB Output is correct
18 Correct 6 ms 600 KB Output is correct
19 Correct 6 ms 600 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 4 ms 344 KB Output is correct
22 Correct 4 ms 344 KB Output is correct
23 Correct 46 ms 3036 KB Output is correct
24 Correct 33 ms 2896 KB Output is correct
25 Correct 130 ms 5224 KB Output is correct
26 Correct 175 ms 7896 KB Output is correct
27 Correct 80 ms 3388 KB Output is correct
28 Correct 20 ms 1548 KB Output is correct
29 Correct 97 ms 4172 KB Output is correct
30 Correct 131 ms 4432 KB Output is correct
31 Correct 121 ms 5796 KB Output is correct
32 Correct 156 ms 6580 KB Output is correct
33 Correct 222 ms 8520 KB Output is correct
34 Correct 152 ms 6564 KB Output is correct
35 Correct 160 ms 6244 KB Output is correct
36 Correct 138 ms 6548 KB Output is correct
37 Correct 143 ms 6368 KB Output is correct
38 Correct 98 ms 4260 KB Output is correct
39 Correct 75 ms 3800 KB Output is correct
40 Correct 67 ms 3332 KB Output is correct
41 Correct 38 ms 1920 KB Output is correct

Subtask #3
29.05 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 504 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 244 ms 11136 KB Output is correct
8 Correct 217 ms 10264 KB Output is correct
9 Partially correct 709 ms 21608 KB Output is partially correct
10 Partially correct 642 ms 29500 KB Output is partially correct
11 Partially correct 247 ms 8976 KB Output is partially correct
12 Correct 168 ms 8592 KB Output is correct
13 Partially correct 317 ms 13164 KB Output is partially correct
14 Partially correct 295 ms 14424 KB Output is partially correct
15 Correct 665 ms 19836 KB Output is correct
16 Partially correct 842 ms 24104 KB Output is partially correct
17 Correct 789 ms 21660 KB Output is correct
18 Partially correct 783 ms 26552 KB Output is partially correct
19 Partially correct 834 ms 26408 KB Output is partially correct
20 Partially correct 897 ms 29452 KB Output is partially correct
21 Partially correct 620 ms 27432 KB Output is partially correct
22 Partially correct 458 ms 23696 KB Output is partially correct
23 Partially correct 258 ms 14336 KB Output is partially correct
24 Correct 346 ms 15508 KB Output is correct
25 Correct 237 ms 12408 KB Output is correct
26 Correct 126 ms 6812 KB Output is correct
27 Correct 507 ms 19696 KB Output is correct
28 Partially correct 605 ms 28324 KB Output is partially correct
29 Partially correct 633 ms 21448 KB Output is partially correct
30 Partially correct 618 ms 22012 KB Output is partially correct
31 Partially correct 645 ms 23764 KB Output is partially correct
32 Partially correct 606 ms 27772 KB Output is partially correct
33 Partially correct 303 ms 15068 KB Output is partially correct
34 Partially correct 294 ms 13424 KB Output is partially correct
35 Partially correct 512 ms 21120 KB Output is partially correct
36 Partially correct 701 ms 23916 KB Output is partially correct
37 Partially correct 554 ms 23720 KB Output is partially correct
38 Partially correct 598 ms 23832 KB Output is partially correct
39 Correct 474 ms 19392 KB Output is correct
40 Partially correct 450 ms 22012 KB Output is partially correct
41 Partially correct 680 ms 24468 KB Output is partially correct
42 Partially correct 579 ms 21980 KB Output is partially correct
43 Partially correct 26 ms 1056 KB Output is partially correct
44 Partially correct 170 ms 6500 KB Output is partially correct
45 Correct 429 ms 10248 KB Output is correct
46 Correct 93 ms 4536 KB Output is correct
47 Correct 207 ms 11084 KB Output is correct
48 Correct 135 ms 8664 KB Output is correct