Submission #1062239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062239		YassirSalama	Counting Mushrooms (IOI20_mushrooms)	C++17	25 / 100	71 ms	592 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define mm use_machine
#define pb push_back
int calc(string s,vector<int> v){
	int ans=0;
    for(int i=0;i+1<(int)v.size();i++){
        if(s[v[i]]!=s[v[i+1]]) ans++;
    }
    return ans;
}
map<int,string> mp;
void make(string s){
	if(s.length()==4){
		mp[calc(s,{0,2,1,3})]=s;
		return;
	}
	make(s+'A');
	make(s+'B');

}
int count_mushrooms(int n) {
	int ans=0;
	string s;
	for(int i=0;i<n;i++) s+='?';
	s[0]='A';
	if(mm({0,1})) s[1]='B';
	else s[1]='A';
	if(n==2){
		return 1+(s[0]==s[1]);
	}
	if(mm({1,2})) s[2]=char(((s[1]-'A')^1)+'A');
	else s[2]=s[1];
	int i=0,j=0;
	for(int a=0;a<=2;a++){
		for(int b=a+1;b<=2;b++){
			if(s[a]==s[b]){
				i=a;
				j=b;
				break;
			}
		}
	}
	string t;
	t+=s[i];t+=s[j];
	make(t);
	for(int k=3;k<n;k+=2){
		if(k+1<n){
			int x=mm({i,k,j,k+1});
			string t = mp[x];
			s[k]=t[2];
			s[k+1]=t[3];
		}else{
			int x=mm({k,k-1});
			if(x){
				s[k]=char(((s[k-1]-'A')^1)+'A');
			}else s[k]=s[k-1];

		}
	}
	for(auto x:s){
		ans+=x=='A';
	}
	return ans;
}

• Subtask 1: 25 / 100