oj.uz

Submission #1078325

# Submission time Handle Problem Language Result Execution time Memory
1078325 2024-08-27T15:20:02 Z Faisal_Saqib Rarest Insects (IOI22_insects) C++17
100 / 100
 504 ms 16216 KB 
#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define all(x) begin(x),end(x)
#define SHUFFLE(v) shuffle(all(v), RNG); 
set<int> machine,rem,real_;
void add(int x)
{
	if(machine.find(x)==machine.end())
	{
		machine.insert(x);
	}
}
void remp(int x)
{
	if(machine.find(x)!=machine.end())
	{
		machine.erase(x);
	}
}
map<vector<int>,int> store;
int ask()
{
	vector<int> cur(begin(machine),end(machine));
	if(store.find(cur)!=store.end())
		return store[cur];
	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;
	return store[cur]=press_button();
}
int min_cardinality(int n)
{

	for(int i=0;i<n;i++){rem.insert(i);}
	{
		vector<int> order(begin(rem),end(rem));
		add(order[0]);
		for(int i=1;i<n;i++)
		{
			add(order[i]);
			if(ask()>1)
			{
				remp(order[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;
		vector<int> order(begin(rem),end(rem));
		SHUFFLE(order);
		for(auto&i:order)
		{
			if(machine.size()==(sz*mid))
				break;
			add(i);
			if(machine.size()>mid and ask()>mid)
			{
				remp(i);
			}
			else
			{
				cur.push_back(i);
				if(machine.size()==(sz*mid))
					break;
			}
		}
		if(machine.size()==((sz*mid)))
		{
			s=mid;
			for(auto&i:cur)
				rem.erase(i);
		}
		else{
			int szp=machine.size();
			e=min(mid,1+(szp/sz));
			rem.clear();
			for(auto&i:cur)
			{
				rem.insert(i);
				remp(i);
			}
		}
	}
	return s;
}

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:66:21: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |    if(machine.size()==(sz*mid))
      |       ~~~~~~~~~~~~~~^~~~~~~~~~
insects.cpp:69:21: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |    if(machine.size()>mid and ask()>mid)
      |       ~~~~~~~~~~~~~~^~~~
insects.cpp:76:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |     if(machine.size()==(sz*mid))
      |        ~~~~~~~~~~~~~~^~~~~~~~~~
insects.cpp:80:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |   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 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 1 ms 344 KB Output is correct
7 Correct 3 ms 728 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 6 ms 464 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 4 ms 596 KB Output is correct
15 Correct 6 ms 600 KB Output is correct
16 Correct 4 ms 600 KB Output is correct
17 Correct 4 ms 604 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 5 ms 600 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 7 ms 344 KB Output is correct
22 Correct 2 ms 452 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 1 ms 344 KB Output is correct
7 Correct 3 ms 728 KB Output is correct
8 Correct 5 ms 600 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 6 ms 464 KB Output is correct
13 Correct 5 ms 600 KB Output is correct
14 Correct 4 ms 596 KB Output is correct
15 Correct 6 ms 600 KB Output is correct
16 Correct 4 ms 600 KB Output is correct
17 Correct 4 ms 604 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 5 ms 600 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 7 ms 344 KB Output is correct
22 Correct 2 ms 452 KB Output is correct
23 Correct 6 ms 844 KB Output is correct
24 Correct 43 ms 2976 KB Output is correct
25 Correct 86 ms 4032 KB Output is correct
26 Correct 97 ms 4176 KB Output is correct
27 Correct 22 ms 1288 KB Output is correct
28 Correct 22 ms 1464 KB Output is correct
29 Correct 51 ms 2384 KB Output is correct
30 Correct 53 ms 3216 KB Output is correct
31 Correct 57 ms 3664 KB Output is correct
32 Correct 79 ms 3988 KB Output is correct
33 Correct 65 ms 4040 KB Output is correct
34 Correct 84 ms 3844 KB Output is correct
35 Correct 77 ms 3856 KB Output is correct
36 Correct 70 ms 4004 KB Output is correct
37 Correct 76 ms 4176 KB Output is correct
38 Correct 56 ms 2876 KB Output is correct
39 Correct 56 ms 3148 KB Output is correct
40 Correct 59 ms 3076 KB Output is correct
41 Correct 39 ms 2128 KB Output is correct

Subtask #3
75.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 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 14 ms 732 KB Output is correct
8 Correct 274 ms 10576 KB Output is correct
9 Correct 445 ms 14960 KB Output is correct
10 Correct 482 ms 15264 KB Output is correct
11 Correct 72 ms 3920 KB Output is correct
12 Correct 216 ms 9104 KB Output is correct
13 Correct 149 ms 6740 KB Output is correct
14 Correct 218 ms 9164 KB Output is correct
15 Correct 422 ms 12656 KB Output is correct
16 Correct 377 ms 13884 KB Output is correct
17 Correct 431 ms 14764 KB Output is correct
18 Correct 447 ms 13376 KB Output is correct
19 Correct 444 ms 13824 KB Output is correct
20 Correct 468 ms 14928 KB Output is correct
21 Correct 440 ms 15124 KB Output is correct
22 Correct 286 ms 12124 KB Output is correct
23 Correct 235 ms 10040 KB Output is correct
24 Correct 342 ms 13388 KB Output is correct
25 Correct 327 ms 11848 KB Output is correct
26 Correct 157 ms 7092 KB Output is correct
27 Correct 447 ms 14724 KB Output is correct
28 Correct 438 ms 14412 KB Output is correct
29 Correct 442 ms 14672 KB Output is correct
30 Correct 407 ms 13788 KB Output is correct
31 Correct 496 ms 16120 KB Output is correct
32 Correct 474 ms 16024 KB Output is correct
33 Correct 246 ms 10464 KB Output is correct
34 Correct 242 ms 10264 KB Output is correct
35 Correct 504 ms 15748 KB Output is correct
36 Correct 444 ms 15268 KB Output is correct
37 Correct 466 ms 15288 KB Output is correct
38 Correct 466 ms 16216 KB Output is correct
39 Correct 473 ms 16000 KB Output is correct
40 Correct 428 ms 15064 KB Output is correct
41 Correct 453 ms 14848 KB Output is correct
42 Correct 462 ms 15772 KB Output is correct
43 Correct 9 ms 856 KB Output is correct
44 Correct 66 ms 2600 KB Output is correct
45 Correct 253 ms 10320 KB Output is correct
46 Correct 150 ms 7036 KB Output is correct
47 Correct 257 ms 10668 KB Output is correct
48 Correct 210 ms 8848 KB Output is correct