Submission #824755

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
824755	2023-08-14T09:40:07 Z	fatemetmhr	Counting Mushrooms (IOI20_mushrooms)	C++17	80.427 / 100	7 ms	312 KB

mushrooms

// Be name khoda //

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << "(" << #x << "):" << x << endl;
#define all(x)   x.begin(), x.end();
#define fi       first
#define se       second
#define pb       push_back
#define mp       make_pair

const int ssq   = 141;
const int maxn5 = 1e5 + 10;


vector <int> av, av2;
int cnt[2], ty[maxn5];

int count_mushrooms(int n){

	av = {0, 1};
	int a = use_machine(av);
	ty[0] = 0;
	ty[1] = a;
	if(n == 2){
		if(a)
			return 1;
		return 2;
	}
	av = {0, 2};
	int b = use_machine(av);
	ty[2] = b;
	int x1, x2;
	if(a == 0){
		x1 = 0;
		x2 = 1;
	}
	else if(b == 0){
		x1 = 0;
		x2 = 2;
	}
	else{
		x1 = 1;
		x2 = 2;
	}
	//cout << x1 << ' ' << x2 << endl;

	cnt[0] = 1 + (1 ^ ty[2]) + (1 ^ ty[1]);
	cnt[1] = ty[2] + ty[1];
	int pt = 3;
	while(max(cnt[0], cnt[1]) < ssq && cnt[0] + cnt[1] < n){
		if(pt + 1 == n){
			av = {x1, pt};
			int x = use_machine(av);
			ty[pt] = (ty[x1] ^ x);
			cnt[ty[pt]]++;
			pt++;
			continue;
		}
		av = {x1, pt, x2, pt + 1};
		int x = use_machine(av);
		if(x == 0){
			ty[pt] = ty[pt + 1] = ty[x1];
			cnt[ty[x1]] += 2;
		}
		if(x == 1){
			ty[pt] = ty[x1];
			ty[pt + 1] = ty[x1] ^ 1;
			cnt[ty[x1]]++;
			cnt[ty[x1] ^ 1]++;
		}
		if(x == 2){
			ty[pt] = ty[x1] ^ 1;
			ty[pt + 1] = ty[x1];
			cnt[ty[x1]]++;
			cnt[ty[x1] ^ 1]++;
		}
		if(x == 3){
			ty[pt] = ty[pt + 1] = ty[x1] ^ 1;
			cnt[ty[x1] ^ 1] += 2;
		}
		pt += 2;
	}

	if(cnt[0] + cnt[1] == n)
		return cnt[0];
	int g = 0;
	if(cnt[1] > cnt[0])
		g = 1;
	for(int i = 0; i < pt; i++) if(ty[i] == g)
		av2.pb(i);
	//cout << pt << ' ' << g << ' ' << av2.size() << endl;
	while(pt < n){
		av.clear();
		int ind = 0;
		while(pt < n && ind < av2.size()){
			av.pb(av2[ind++]);
			av.pb(pt++);
		}
		int x = use_machine(av);
		int num = x / 2 + x % 2;
		cnt[g ^ 1] += num;
		cnt[g] += int(av.size()) / 2 - num;
	}
	return cnt[0];
}

Compilation message

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   while(pt < n && ind < av2.size()){
      |                   ~~~~^~~~~~~~~~~~

Subtask #1

80.427 / 100.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	2 ms	208 KB	Output is correct
7	Correct	5 ms	208 KB	Output is correct
8	Correct	5 ms	208 KB	Output is correct
9	Correct	5 ms	208 KB	Output is correct
10	Partially correct	6 ms	208 KB	Output is partially correct
11	Partially correct	5 ms	208 KB	Output is partially correct
12	Partially correct	5 ms	208 KB	Output is partially correct
13	Correct	5 ms	208 KB	Output is correct
14	Correct	3 ms	208 KB	Output is correct
15	Partially correct	5 ms	208 KB	Output is partially correct
16	Partially correct	5 ms	208 KB	Output is partially correct
17	Correct	4 ms	208 KB	Output is correct
18	Correct	6 ms	208 KB	Output is correct
19	Partially correct	7 ms	208 KB	Output is partially correct
20	Partially correct	5 ms	208 KB	Output is partially correct
21	Partially correct	4 ms	312 KB	Output is partially correct
22	Partially correct	5 ms	208 KB	Output is partially correct
23	Partially correct	7 ms	208 KB	Output is partially correct
24	Correct	4 ms	208 KB	Output is correct
25	Partially correct	5 ms	208 KB	Output is partially correct
26	Partially correct	5 ms	208 KB	Output is partially correct
27	Partially correct	5 ms	208 KB	Output is partially correct
28	Partially correct	5 ms	208 KB	Output is partially correct
29	Partially correct	5 ms	308 KB	Output is partially correct
30	Partially correct	5 ms	208 KB	Output is partially correct
31	Partially correct	5 ms	208 KB	Output is partially correct
32	Partially correct	7 ms	308 KB	Output is partially correct
33	Partially correct	5 ms	208 KB	Output is partially correct
34	Partially correct	4 ms	308 KB	Output is partially correct
35	Partially correct	5 ms	312 KB	Output is partially correct
36	Partially correct	6 ms	312 KB	Output is partially correct
37	Partially correct	5 ms	208 KB	Output is partially correct
38	Partially correct	7 ms	208 KB	Output is partially correct
39	Partially correct	5 ms	208 KB	Output is partially correct
40	Partially correct	6 ms	208 KB	Output is partially correct
41	Partially correct	5 ms	208 KB	Output is partially correct
42	Partially correct	4 ms	208 KB	Output is partially correct
43	Partially correct	5 ms	208 KB	Output is partially correct
44	Partially correct	5 ms	312 KB	Output is partially correct
45	Partially correct	6 ms	208 KB	Output is partially correct
46	Partially correct	5 ms	208 KB	Output is partially correct
47	Partially correct	5 ms	208 KB	Output is partially correct
48	Partially correct	5 ms	208 KB	Output is partially correct
49	Partially correct	5 ms	312 KB	Output is partially correct
50	Partially correct	6 ms	208 KB	Output is partially correct
51	Partially correct	5 ms	208 KB	Output is partially correct
52	Partially correct	6 ms	208 KB	Output is partially correct
53	Partially correct	7 ms	308 KB	Output is partially correct
54	Partially correct	5 ms	208 KB	Output is partially correct
55	Partially correct	6 ms	208 KB	Output is partially correct
56	Partially correct	5 ms	208 KB	Output is partially correct
57	Partially correct	5 ms	208 KB	Output is partially correct
58	Partially correct	5 ms	208 KB	Output is partially correct
59	Partially correct	5 ms	208 KB	Output is partially correct
60	Partially correct	5 ms	208 KB	Output is partially correct
61	Partially correct	5 ms	208 KB	Output is partially correct
62	Correct	0 ms	208 KB	Output is correct
63	Correct	0 ms	208 KB	Output is correct
64	Correct	0 ms	208 KB	Output is correct
65	Correct	0 ms	208 KB	Output is correct
66	Correct	0 ms	208 KB	Output is correct
67	Correct	1 ms	208 KB	Output is correct
68	Correct	0 ms	208 KB	Output is correct
69	Correct	0 ms	208 KB	Output is correct
70	Correct	0 ms	208 KB	Output is correct
71	Correct	0 ms	208 KB	Output is correct
72	Correct	0 ms	208 KB	Output is correct
73	Correct	0 ms	208 KB	Output is correct
74	Correct	0 ms	208 KB	Output is correct
75	Correct	1 ms	208 KB	Output is correct
76	Correct	0 ms	208 KB	Output is correct
77	Correct	0 ms	208 KB	Output is correct
78	Correct	1 ms	208 KB	Output is correct
79	Correct	0 ms	208 KB	Output is correct
80	Correct	0 ms	208 KB	Output is correct
81	Correct	0 ms	208 KB	Output is correct
82	Correct	0 ms	208 KB	Output is correct
83	Correct	0 ms	208 KB	Output is correct
84	Correct	0 ms	208 KB	Output is correct
85	Correct	0 ms	208 KB	Output is correct
86	Correct	0 ms	208 KB	Output is correct
87	Correct	0 ms	208 KB	Output is correct
88	Correct	0 ms	208 KB	Output is correct
89	Correct	0 ms	208 KB	Output is correct
90	Correct	0 ms	208 KB	Output is correct
91	Correct	0 ms	208 KB	Output is correct