Submission #412207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412207	2021-05-26T15:39:45 Z	mosiashvililuka	Counting Mushrooms (IOI20_mushrooms)	C++17	92.623 / 100	11 ms	432 KB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,A,B,cnt;
int T=80;
int SUB;
string QWE;
vector <int> vA,vB,vv;
/*int use_machine(vector <int> q){
	int we=0;
	for(int qw=1; qw<q.size(); qw++){
		if(QWE[q[qw]]!=QWE[q[qw-1]]){
			we++;
		}
	}
	return we;
}*/
int bruteforce(int n){
	a=n;
	vA.push_back(0);
	A++;
	for(i=1; i<a; i++){
		//if(vA.size()>=T||vB.size()>=T) break;
		vv.clear();vv.push_back(0);vv.push_back(i);
		c=use_machine(vv);
		if(c==0){
			vA.push_back(i);
			A++;
		}else{
			vB.push_back(i);
			B++;
		}
	}
	return A;
}
int count_mushrooms(int n) {
	if(n<=220){
		return bruteforce(n);
	}
	a=n;
	vA.push_back(0);
	A++;
	//
	vv.clear();vv.push_back(0);vv.push_back(1);
	c=use_machine(vv);
	if(c==0){
		vA.push_back(1);
		A++;
	}else{
		vB.push_back(1);
		B++;
	}
	vv.clear();vv.push_back(0);vv.push_back(2);
	c=use_machine(vv);
	if(c==0){
		vA.push_back(2);
		A++;
	}else{
		vB.push_back(2);
		B++;
	}
	if(vA.size()>=vB.size()){
		
	}else{
		SUB^=1;
		swap(vA,vB);
		swap(A,B);
	}
	//
	cnt=3;
	for(i=cnt; i<a; i+=2){
		if(vA.size()>=T||vB.size()>=T) break;
		vv.clear();vv.push_back(vA[0]);vv.push_back(i);
		vv.push_back(vA[1]);vv.push_back(i+1);
		c=use_machine(vv);
		if(c/2==0){
			vA.push_back(i);
			A++;
		}else{
			vB.push_back(i);
			B++;
		}
		if(c%2==0){
			vA.push_back(i+1);
			A++;
		}else{
			vB.push_back(i+1);
			B++;
		}
		cnt+=2;
	}
	if(vA.size()>=T){
		
	}else{
		SUB^=1;
		swap(vA,vB);
		swap(A,B);
	}
	while(cnt<a){
		vv.clear();
		e=cnt;d=0;
		for(i=e; i<e+vA.size(); i++){
			if(i>=a) break;
			vv.push_back(vA[i-e]);
			vv.push_back(i);
			d++;
			cnt++;
		}
		c=use_machine(vv);
		zx=c/2+c%2;
		B+=zx;
		A+=(d-zx);
		if(c%2==0){
			vA.push_back(cnt-1);
		}else{
			vB.push_back(cnt-1);
		}
		if(vA.size()>=vB.size()){
			
		}else{
			SUB^=1;
			swap(vA,vB);
			swap(A,B);
		}
	}
	if(SUB==1) A=n-A;
	return A;
}
 
/*int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	//cin>>a;
	cin>>QWE;
	zx=0;
	for(i=0; i<QWE.size(); i++){
		if(QWE[i]=='A'){
			zx++;
		}
	}
	cout<<"A: "<<zx<<endl;
	cout<<count_mushrooms(QWE.size());
	return 0;
}*/

Compilation message

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:72:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |   if(vA.size()>=T||vB.size()>=T) break;
      |      ~~~~~~~~~^~~
mushrooms.cpp:72:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |   if(vA.size()>=T||vB.size()>=T) break;
      |                    ~~~~~~~~~^~~
mushrooms.cpp:92:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |  if(vA.size()>=T){
      |     ~~~~~~~~~^~~
mushrooms.cpp:102:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(i=e; i<e+vA.size(); i++){
      |            ~^~~~~~~~~~~~

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	3 ms	200 KB	Output is correct
6	Correct	2 ms	200 KB	Output is correct
7	Correct	8 ms	200 KB	Output is correct
8	Correct	7 ms	200 KB	Output is correct
9	Correct	9 ms	328 KB	Output is correct
10	Correct	9 ms	324 KB	Output is correct
11	Partially correct	8 ms	316 KB	Output is partially correct
12	Correct	7 ms	200 KB	Output is correct
13	Correct	8 ms	200 KB	Output is correct
14	Correct	5 ms	200 KB	Output is correct
15	Partially correct	8 ms	312 KB	Output is partially correct
16	Partially correct	9 ms	328 KB	Output is partially correct
17	Correct	5 ms	304 KB	Output is correct
18	Correct	7 ms	200 KB	Output is correct
19	Partially correct	9 ms	200 KB	Output is partially correct
20	Correct	7 ms	200 KB	Output is correct
21	Correct	7 ms	316 KB	Output is correct
22	Partially correct	8 ms	320 KB	Output is partially correct
23	Correct	7 ms	312 KB	Output is correct
24	Correct	5 ms	200 KB	Output is correct
25	Partially correct	7 ms	200 KB	Output is partially correct
26	Partially correct	8 ms	300 KB	Output is partially correct
27	Partially correct	8 ms	312 KB	Output is partially correct
28	Partially correct	8 ms	200 KB	Output is partially correct
29	Partially correct	9 ms	432 KB	Output is partially correct
30	Partially correct	8 ms	200 KB	Output is partially correct
31	Partially correct	8 ms	316 KB	Output is partially correct
32	Partially correct	8 ms	316 KB	Output is partially correct
33	Partially correct	9 ms	308 KB	Output is partially correct
34	Partially correct	7 ms	320 KB	Output is partially correct
35	Partially correct	7 ms	308 KB	Output is partially correct
36	Partially correct	7 ms	320 KB	Output is partially correct
37	Partially correct	8 ms	316 KB	Output is partially correct
38	Partially correct	8 ms	200 KB	Output is partially correct
39	Partially correct	9 ms	200 KB	Output is partially correct
40	Partially correct	8 ms	200 KB	Output is partially correct
41	Partially correct	7 ms	320 KB	Output is partially correct
42	Partially correct	7 ms	316 KB	Output is partially correct
43	Partially correct	6 ms	328 KB	Output is partially correct
44	Partially correct	9 ms	200 KB	Output is partially correct
45	Partially correct	11 ms	328 KB	Output is partially correct
46	Partially correct	8 ms	328 KB	Output is partially correct
47	Partially correct	10 ms	200 KB	Output is partially correct
48	Partially correct	7 ms	296 KB	Output is partially correct
49	Partially correct	8 ms	200 KB	Output is partially correct
50	Partially correct	8 ms	200 KB	Output is partially correct
51	Partially correct	10 ms	324 KB	Output is partially correct
52	Partially correct	8 ms	200 KB	Output is partially correct
53	Partially correct	10 ms	312 KB	Output is partially correct
54	Partially correct	7 ms	200 KB	Output is partially correct
55	Partially correct	8 ms	320 KB	Output is partially correct
56	Partially correct	6 ms	328 KB	Output is partially correct
57	Partially correct	7 ms	324 KB	Output is partially correct
58	Partially correct	8 ms	324 KB	Output is partially correct
59	Partially correct	8 ms	312 KB	Output is partially correct
60	Partially correct	8 ms	320 KB	Output is partially correct
61	Partially correct	8 ms	200 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