Submission #396245

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
396245	2021-04-29T15:28:44 Z	faresbasbs	Counting Mushrooms (IOI20_mushrooms)	C++14	92.623 / 100	12 ms	456 KB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
const int sq = 83;
vector<int> a,b;
int n;
 
int ask(vector<int> v){
	return use_machine(v);
}
 
int base(){
	int ret = 1 , pos = 1;
	if(n%2 == 0){
		pos = 2;
		vector<int> f = {0,1};
		ret += 1-ask(f);
	}
	for(int i = pos ; i < n ; i += 2){
		vector<int> f = {i,0,i+1};
		ret += 2-ask(f);
	}
	return ret;
}
 
void step1(){
	a = {0};
	vector<int> f = {0,1} , f2 = {0,2};
	if(ask(f) == 0){
		a.push_back(1);
	}else{
		b.push_back(1);
	}
	if(ask(f2) == 0){
		a.push_back(2);
	}else{
		b.push_back(2);
	}
}
 
void step2(){
	if(a.size() >= 2){
		for(int i = 3 ; i < 2*sq ; i += 2){
			vector<int> f = {a[0],i,a[1],i+1};
			int num = ask(f);
			if(num == 0){
				a.push_back(i),a.push_back(i+1);
			}else if(num == 1){
				a.push_back(i),b.push_back(i+1);
			}else if(num == 2){
				b.push_back(i),a.push_back(i+1);
			}else{
				b.push_back(i),b.push_back(i+1);
			}
		}
	}else{
		for(int i = 3 ; i < 2*sq ; i += 2){
			vector<int> f = {b[0],i,b[1],i+1};
			int num = ask(f);
			if(num == 0){
				b.push_back(i),b.push_back(i+1);
			}else if(num == 1){
				b.push_back(i),a.push_back(i+1);
			}else if(num == 2){
				a.push_back(i),b.push_back(i+1);
			}else{
				a.push_back(i),a.push_back(i+1);
			}
		}
	}
}
 
int sv1(int pos){
	int num = 0;
	vector<int> f;
	for(int i = 0 , j = pos ; i < a.size() && j < n ; i += 1 , j += 1){
		f.push_back(a[i]),f.push_back(j),num += 1;
	}
	num -= 1;
	int val = ask(f);
	if(val%2 == 0){
		a.push_back(f.back());
	}else{
		b.push_back(f.back());
	}
	return num-val/2;
}
 
int sv2(int pos){
	int num = 0;
	vector<int> f;
	for(int i = 0 , j = pos ; i < b.size() && j < n ; i += 1 , j += 1){
		f.push_back(b[i]),f.push_back(j),num += 1;
	}
	num -= 1;
	int val = ask(f);
	if(val%2 == 0){
		b.push_back(f.back());
	}else{
		a.push_back(f.back());
	}
	return val/2;
}
 
int step3(){
	int ret = 0 , pos = 2*sq+1;
	while(pos < n){
		if(a.size() > b.size()){
			int nxt = pos+a.size();
			ret += sv1(pos);
			pos = nxt;
		}else{
			int nxt = pos+b.size();
			ret += sv2(pos);
			pos = nxt;
		}
	}
	return ret;
}
 
int count_mushrooms(int N){
	n = N;
	if(n <= 400){
		return base();
	}
	step1();
	step2();
	return step3()+a.size();
}

Compilation message

mushrooms.cpp: In function 'int sv1(int)':
mushrooms.cpp:76:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0 , j = pos ; i < a.size() && j < n ; i += 1 , j += 1){
      |                            ~~^~~~~~~~~~
mushrooms.cpp: In function 'int sv2(int)':
mushrooms.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0 , j = pos ; i < b.size() && j < n ; i += 1 , j += 1){
      |                            ~~^~~~~~~~~~

Subtask #1

92.623 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Output is correct
2	Correct	1 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	1 ms	200 KB	Output is correct
6	Correct	2 ms	200 KB	Output is correct
7	Correct	7 ms	200 KB	Output is correct
8	Correct	7 ms	200 KB	Output is correct
9	Correct	8 ms	200 KB	Output is correct
10	Correct	7 ms	328 KB	Output is correct
11	Partially correct	8 ms	332 KB	Output is partially correct
12	Correct	9 ms	328 KB	Output is correct
13	Correct	10 ms	304 KB	Output is correct
14	Correct	5 ms	332 KB	Output is correct
15	Partially correct	8 ms	324 KB	Output is partially correct
16	Partially correct	7 ms	328 KB	Output is partially correct
17	Correct	5 ms	200 KB	Output is correct
18	Correct	8 ms	200 KB	Output is correct
19	Partially correct	9 ms	328 KB	Output is partially correct
20	Correct	9 ms	200 KB	Output is correct
21	Correct	8 ms	328 KB	Output is correct
22	Partially correct	7 ms	328 KB	Output is partially correct
23	Correct	7 ms	200 KB	Output is correct
24	Correct	7 ms	328 KB	Output is correct
25	Partially correct	12 ms	328 KB	Output is partially correct
26	Partially correct	8 ms	456 KB	Output is partially correct
27	Partially correct	8 ms	328 KB	Output is partially correct
28	Partially correct	9 ms	328 KB	Output is partially correct
29	Partially correct	8 ms	328 KB	Output is partially correct
30	Partially correct	9 ms	340 KB	Output is partially correct
31	Partially correct	9 ms	328 KB	Output is partially correct
32	Partially correct	9 ms	344 KB	Output is partially correct
33	Partially correct	9 ms	332 KB	Output is partially correct
34	Partially correct	8 ms	328 KB	Output is partially correct
35	Partially correct	9 ms	328 KB	Output is partially correct
36	Partially correct	8 ms	320 KB	Output is partially correct
37	Partially correct	7 ms	308 KB	Output is partially correct
38	Partially correct	8 ms	328 KB	Output is partially correct
39	Partially correct	9 ms	336 KB	Output is partially correct
40	Partially correct	9 ms	328 KB	Output is partially correct
41	Partially correct	9 ms	328 KB	Output is partially correct
42	Partially correct	8 ms	336 KB	Output is partially correct
43	Partially correct	11 ms	328 KB	Output is partially correct
44	Partially correct	9 ms	332 KB	Output is partially correct
45	Partially correct	8 ms	328 KB	Output is partially correct
46	Partially correct	9 ms	328 KB	Output is partially correct
47	Partially correct	9 ms	328 KB	Output is partially correct
48	Partially correct	10 ms	328 KB	Output is partially correct
49	Partially correct	7 ms	300 KB	Output is partially correct
50	Partially correct	9 ms	316 KB	Output is partially correct
51	Partially correct	11 ms	328 KB	Output is partially correct
52	Partially correct	8 ms	332 KB	Output is partially correct
53	Partially correct	12 ms	328 KB	Output is partially correct
54	Partially correct	9 ms	328 KB	Output is partially correct
55	Partially correct	8 ms	320 KB	Output is partially correct
56	Partially correct	9 ms	328 KB	Output is partially correct
57	Partially correct	9 ms	360 KB	Output is partially correct
58	Partially correct	8 ms	348 KB	Output is partially correct
59	Partially correct	8 ms	316 KB	Output is partially correct
60	Partially correct	8 ms	328 KB	Output is partially correct
61	Partially correct	9 ms	316 KB	Output is partially correct
62	Correct	1 ms	200 KB	Output is correct
63	Correct	1 ms	200 KB	Output is correct
64	Correct	1 ms	200 KB	Output is correct
65	Correct	1 ms	200 KB	Output is correct
66	Correct	1 ms	200 KB	Output is correct
67	Correct	1 ms	200 KB	Output is correct
68	Correct	1 ms	200 KB	Output is correct
69	Correct	1 ms	200 KB	Output is correct
70	Correct	1 ms	200 KB	Output is correct
71	Correct	1 ms	200 KB	Output is correct
72	Correct	1 ms	200 KB	Output is correct
73	Correct	1 ms	200 KB	Output is correct
74	Correct	1 ms	200 KB	Output is correct
75	Correct	1 ms	200 KB	Output is correct
76	Correct	1 ms	200 KB	Output is correct
77	Correct	1 ms	200 KB	Output is correct
78	Correct	1 ms	200 KB	Output is correct
79	Correct	1 ms	200 KB	Output is correct
80	Correct	1 ms	200 KB	Output is correct
81	Correct	1 ms	200 KB	Output is correct
82	Correct	1 ms	200 KB	Output is correct
83	Correct	1 ms	200 KB	Output is correct
84	Correct	1 ms	200 KB	Output is correct
85	Correct	1 ms	200 KB	Output is correct
86	Correct	1 ms	200 KB	Output is correct
87	Correct	1 ms	200 KB	Output is correct
88	Correct	1 ms	200 KB	Output is correct
89	Correct	1 ms	200 KB	Output is correct
90	Correct	1 ms	200 KB	Output is correct
91	Correct	1 ms	200 KB	Output is correct