Submission #412181

#	Time	Username	Problem	Language	Result	Execution time	Memory
412181		mosiashvililuka	Counting Mushrooms (IOI20_mushrooms)	C++17	85.93 / 100	12 ms	460 KiB

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=50;
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;
		A+=(d-zx);
		if(c%2==0){
			vA.push_back(cnt-1);
		}
	}
	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 (stderr)

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: 85.9316 / 100