oj.uz

Submission #1078236

# Submission time Handle Problem Language Result Execution time Memory
1078236 2024-08-27T14:22:04 Z Faisal_Saqib Rarest Insects (IOI22_insects) C++17
93 / 100
 937 ms 21632 KB 
#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
set<int> machine,rem,real_;
int sm=0;
void add(int x)
{
	if(machine.find(x)==machine.end())
	{
		// move_inside(x);
		machine.insert(x);
	}
}
void remp(int x)
{
	if(machine.find(x)!=machine.end())
	{
		// move_outside(x);
		machine.erase(x);
	}
}
map<vector<int>,int> store;
int ask()
{
	for(auto&i:real_)
	{
		if(machine.find(i)==machine.end())
		{
			move_outside(i);
		}	
	}
	for(auto&i:machine)
	{
		if(real_.find(i)==real_.end())
		{
			move_inside(i);
		}
	}
	real_=machine;
	vector<int> cur(begin(machine),end(machine));
	if(store.find(cur)==store.end())
		store[cur]=press_button();
	// cout<<"Query for: ";
	// for(auto j:cur)
	// {
	// 	cout<<j<<' ';
	// }
	// cout<<" ans: "<<store[cur]<<endl;
	return store[cur];
}
int min_cardinality(int n)
{
	add(0);
	for(int i=1;i<n;i++)
	{
		add(i);
		if(ask()>1)
		{
			rem.insert(i);
			remp(i);
		}
	}
	int sz=machine.size();
	int s=1;
	int e=(n/sz)+1;
	while(s+1<e)
	{
		int mid=(s+e)/2;
		vector<int> cur;
		// cout<<endl;
		// cout<<"for "<<mid<<endl;
		// cout<<"\nMachine: ";
		// for(auto j:machine)
		// {
		// 	cout<<j<<' ';
		// }
		// cout<<endl;
		for(auto&i:rem)
		{
			// cout<<"Add and query "<<i<<endl;
			add(i);
			if(ask()>mid)
			{
				remp(i);
			}
			else
			{
				cur.push_back(i);
				if(machine.size()==(sz*mid))
					break;
			}
		}
		if(machine.size()==((sz*mid)))
		{
			s=mid;
			//	 We can make values in amachin so keep
			for(auto&i:cur)
				rem.erase(i);
		}
		else{
			e=mid;
			rem.clear();
			for(auto&i:machine)
				rem.insert(i);
			for(auto&i:rem)
				remp(i);
		}
	}
	return s;
}

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:91:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |     if(machine.size()==(sz*mid))
      |        ~~~~~~~~~~~~~~^~~~~~~~~~
insects.cpp:95:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |   if(machine.size()==((sz*mid)))
      |      ~~~~~~~~~~~~~~^~~~~~~~~~~~

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 1 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 4 ms 344 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 5 ms 472 KB Output is correct
10 Correct 3 ms 448 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 6 ms 544 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 7 ms 656 KB Output is correct
15 Correct 7 ms 612 KB Output is correct
16 Correct 7 ms 476 KB Output is correct
17 Correct 7 ms 856 KB Output is correct
18 Correct 5 ms 472 KB Output is correct
19 Correct 6 ms 612 KB Output is correct
20 Correct 7 ms 600 KB Output is correct
21 Correct 3 ms 344 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 1 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 4 ms 344 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 5 ms 472 KB Output is correct
10 Correct 3 ms 448 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 6 ms 544 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 7 ms 656 KB Output is correct
15 Correct 7 ms 612 KB Output is correct
16 Correct 7 ms 476 KB Output is correct
17 Correct 7 ms 856 KB Output is correct
18 Correct 5 ms 472 KB Output is correct
19 Correct 6 ms 612 KB Output is correct
20 Correct 7 ms 600 KB Output is correct
21 Correct 3 ms 344 KB Output is correct
22 Correct 2 ms 344 KB Output is correct
23 Correct 56 ms 2880 KB Output is correct
24 Correct 55 ms 2864 KB Output is correct
25 Correct 96 ms 4028 KB Output is correct
26 Correct 142 ms 5456 KB Output is correct
27 Correct 36 ms 1700 KB Output is correct
28 Correct 24 ms 1616 KB Output is correct
29 Correct 48 ms 2124 KB Output is correct
30 Correct 71 ms 2900 KB Output is correct
31 Correct 126 ms 4592 KB Output is correct
32 Correct 210 ms 5916 KB Output is correct
33 Correct 173 ms 6024 KB Output is correct
34 Correct 113 ms 4736 KB Output is correct
35 Correct 117 ms 4968 KB Output is correct
36 Correct 115 ms 4304 KB Output is correct
37 Correct 116 ms 4804 KB Output is correct
38 Correct 66 ms 3104 KB Output is correct
39 Correct 71 ms 3408 KB Output is correct
40 Correct 61 ms 3144 KB Output is correct
41 Correct 44 ms 2012 KB Output is correct

Subtask #3
68.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 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 432 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 295 ms 10792 KB Output is correct
8 Correct 281 ms 10208 KB Output is correct
9 Correct 538 ms 15404 KB Output is correct
10 Partially correct 674 ms 19768 KB Output is partially correct
11 Correct 111 ms 5048 KB Output is correct
12 Correct 189 ms 8688 KB Output is correct
13 Correct 193 ms 7272 KB Output is correct
14 Correct 228 ms 9044 KB Output is correct
15 Partially correct 902 ms 17084 KB Output is partially correct
16 Partially correct 937 ms 19964 KB Output is partially correct
17 Partially correct 916 ms 17092 KB Output is partially correct
18 Partially correct 881 ms 19632 KB Output is partially correct
19 Partially correct 683 ms 18092 KB Output is partially correct
20 Partially correct 899 ms 20884 KB Output is partially correct
21 Partially correct 593 ms 18108 KB Output is partially correct
22 Correct 317 ms 13220 KB Output is correct
23 Correct 272 ms 10136 KB Output is correct
24 Correct 374 ms 13588 KB Output is correct
25 Correct 346 ms 11848 KB Output is correct
26 Correct 177 ms 6952 KB Output is correct
27 Correct 638 ms 19632 KB Output is correct
28 Correct 283 ms 10396 KB Output is correct
29 Correct 751 ms 20736 KB Output is correct
30 Correct 737 ms 20680 KB Output is correct
31 Partially correct 647 ms 15944 KB Output is partially correct
32 Partially correct 661 ms 18792 KB Output is partially correct
33 Correct 319 ms 9396 KB Output is correct
34 Correct 242 ms 9416 KB Output is correct
35 Partially correct 758 ms 21112 KB Output is partially correct
36 Correct 594 ms 16568 KB Output is correct
37 Partially correct 650 ms 15928 KB Output is partially correct
38 Partially correct 743 ms 18272 KB Output is partially correct
39 Correct 646 ms 19552 KB Output is correct
40 Correct 268 ms 10176 KB Output is correct
41 Correct 593 ms 16720 KB Output is correct
42 Partially correct 790 ms 21632 KB Output is partially correct
43 Correct 12 ms 600 KB Output is correct
44 Correct 95 ms 3080 KB Output is correct
45 Correct 314 ms 10968 KB Output is correct
46 Correct 127 ms 6992 KB Output is correct
47 Correct 261 ms 10640 KB Output is correct
48 Correct 179 ms 8648 KB Output is correct