Submission #640851

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
640851	2022-09-15T11:06:11 Z	blue	Rarest Insects (IOI22_insects)	C++17	100 / 100	62 ms	436 KB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

const int mx = 2'000;

vi ins(mx, 0);
int ct = 0;

int getRandom(int l, int r)
{
	return rand() % (r-l+1);
}

void move_in(int i)
{
	// cerr << "insert " << i << '\n';
	if(ins[i]) 
		return;

	ins[i] = 1;
	move_inside(i);
	ct++;
}

void move_out(int i)
{
	// cerr << "erase " << i << '\n';
	if(!ins[i])
		return;

	ins[i] = 0;
	move_outside(i);
	ct--;
}

int Z = 0; //number of species

int ans = -1;

void solve(vi lst, int b) //b = basic value
{
	if(sz(lst) < Z)
		return;

	int mx = sz(lst)/Z;

	int med = mx - (mx/2);

	vi ins, notins;

	int to_exc = -1;

	bool flag = 0;

	for(int t = 0; t < 10*sz(lst); t++)
	{
		int u = getRandom(0, sz(lst)-1);
		int v = getRandom(0, sz(lst)-1);
		swap(lst[u], lst[v]);
	}

	for(int i : lst)
	{
		if(ct == (med + b) * Z)
		{
			notins.push_back(i);
			continue;
		}

		move_in(i);

		int pb = press_button();

		if(pb - b > med)
		{
			move_out(i);
			notins.push_back(i);
		}
		else
		{
			if(pb - b == med && flag == 0)
			{
				to_exc = i;
				flag = 1;
			}
			ins.push_back(i);
		}
	}

	if(ct == (med + b) * Z)
	{
		solve(notins, b + med);
	}
	else
	{
		if(sz(lst) >= 2*Z)
		{
			for(int i : ins)
				move_out(i);

			vi new_ins;
			for(int i : ins)
				if(i != to_exc)
					new_ins.push_back(i);
			solve(new_ins, b);
		}
		else
			ans = (ct - sz(ins))/Z;
	}
}

int min_cardinality(int N)
{
	vi lst;
	for(int i = 0; i < N; i++)
	{
		move_in(i);
		if(press_button() >= 2)
		{
			move_out(i);
			lst.push_back(i);
		}
		else
			Z++;
	}

	solve(lst, 1);
	if(ans != -1)
		return ans;
	return ct / Z;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	0 ms	208 KB	Output is correct
4	Correct	0 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	3 ms	208 KB	Output is correct
7	Correct	3 ms	208 KB	Output is correct
8	Correct	4 ms	208 KB	Output is correct
9	Correct	5 ms	208 KB	Output is correct
10	Correct	7 ms	208 KB	Output is correct
11	Correct	1 ms	208 KB	Output is correct
12	Correct	3 ms	308 KB	Output is correct
13	Correct	5 ms	208 KB	Output is correct
14	Correct	5 ms	208 KB	Output is correct
15	Correct	5 ms	308 KB	Output is correct
16	Correct	6 ms	208 KB	Output is correct
17	Correct	7 ms	308 KB	Output is correct
18	Correct	5 ms	208 KB	Output is correct
19	Correct	6 ms	304 KB	Output is correct
20	Correct	6 ms	308 KB	Output is correct
21	Correct	3 ms	208 KB	Output is correct
22	Correct	2 ms	208 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	0 ms	208 KB	Output is correct
4	Correct	0 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	3 ms	208 KB	Output is correct
7	Correct	3 ms	208 KB	Output is correct
8	Correct	4 ms	208 KB	Output is correct
9	Correct	5 ms	208 KB	Output is correct
10	Correct	7 ms	208 KB	Output is correct
11	Correct	1 ms	208 KB	Output is correct
12	Correct	3 ms	308 KB	Output is correct
13	Correct	5 ms	208 KB	Output is correct
14	Correct	5 ms	208 KB	Output is correct
15	Correct	5 ms	308 KB	Output is correct
16	Correct	6 ms	208 KB	Output is correct
17	Correct	7 ms	308 KB	Output is correct
18	Correct	5 ms	208 KB	Output is correct
19	Correct	6 ms	304 KB	Output is correct
20	Correct	6 ms	308 KB	Output is correct
21	Correct	3 ms	208 KB	Output is correct
22	Correct	2 ms	208 KB	Output is correct
23	Correct	18 ms	312 KB	Output is correct
24	Correct	10 ms	208 KB	Output is correct
25	Correct	25 ms	300 KB	Output is correct
26	Correct	33 ms	428 KB	Output is correct
27	Correct	25 ms	300 KB	Output is correct
28	Correct	8 ms	208 KB	Output is correct
29	Correct	18 ms	304 KB	Output is correct
30	Correct	24 ms	308 KB	Output is correct
31	Correct	23 ms	308 KB	Output is correct
32	Correct	17 ms	208 KB	Output is correct
33	Correct	19 ms	304 KB	Output is correct
34	Correct	10 ms	312 KB	Output is correct
35	Correct	20 ms	312 KB	Output is correct
36	Correct	20 ms	304 KB	Output is correct
37	Correct	23 ms	312 KB	Output is correct
38	Correct	18 ms	292 KB	Output is correct
39	Correct	17 ms	208 KB	Output is correct
40	Correct	14 ms	208 KB	Output is correct
41	Correct	6 ms	304 KB	Output is correct

Subtask #3
75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	0 ms	208 KB	Output is correct
4	Correct	0 ms	208 KB	Output is correct
5	Correct	0 ms	208 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	24 ms	312 KB	Output is correct
8	Correct	18 ms	208 KB	Output is correct
9	Correct	43 ms	312 KB	Output is correct
10	Correct	56 ms	312 KB	Output is correct
11	Correct	32 ms	312 KB	Output is correct
12	Correct	30 ms	328 KB	Output is correct
13	Correct	53 ms	312 KB	Output is correct
14	Correct	62 ms	308 KB	Output is correct
15	Correct	42 ms	320 KB	Output is correct
16	Correct	41 ms	436 KB	Output is correct
17	Correct	44 ms	308 KB	Output is correct
18	Correct	44 ms	324 KB	Output is correct
19	Correct	47 ms	312 KB	Output is correct
20	Correct	38 ms	324 KB	Output is correct
21	Correct	39 ms	336 KB	Output is correct
22	Correct	47 ms	312 KB	Output is correct
23	Correct	45 ms	300 KB	Output is correct
24	Correct	18 ms	312 KB	Output is correct
25	Correct	30 ms	308 KB	Output is correct
26	Correct	16 ms	208 KB	Output is correct
27	Correct	46 ms	316 KB	Output is correct
28	Correct	37 ms	308 KB	Output is correct
29	Correct	33 ms	208 KB	Output is correct
30	Correct	41 ms	308 KB	Output is correct
31	Correct	34 ms	420 KB	Output is correct
32	Correct	57 ms	312 KB	Output is correct
33	Correct	51 ms	436 KB	Output is correct
34	Correct	47 ms	332 KB	Output is correct
35	Correct	44 ms	316 KB	Output is correct
36	Correct	39 ms	312 KB	Output is correct
37	Correct	41 ms	308 KB	Output is correct
38	Correct	53 ms	328 KB	Output is correct
39	Correct	41 ms	320 KB	Output is correct
40	Correct	47 ms	428 KB	Output is correct
41	Correct	51 ms	300 KB	Output is correct
42	Correct	45 ms	312 KB	Output is correct
43	Correct	10 ms	308 KB	Output is correct
44	Correct	34 ms	320 KB	Output is correct
45	Correct	23 ms	300 KB	Output is correct
46	Correct	24 ms	312 KB	Output is correct
47	Correct	28 ms	208 KB	Output is correct
48	Correct	26 ms	208 KB	Output is correct

Submission #640851

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 15.0 / 15.0

Subtask #3 75.0 / 75.0

Subtask #1
10.0 / 10.0

Subtask #2
15.0 / 15.0

Subtask #3
75.0 / 75.0