Submission #1072243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072243		Itamar	Counting Mushrooms (IOI20_mushrooms)	C++14	48.81 / 100	33 ms	748 KiB

mushrooms

using namespace std;
#include <vector>
#define ll long long
#define vll vector<ll>
#include<iostream>
#define vi vector<int>
int use_machine(std::vector<int> x);
#include<bitset>
	const int k = 15;
int count_mushrooms(int n) {
	vi v[2];
	v[0].push_back(0);
	/*v[use_machine({0,1})].push_back(1);
	if(n==2)return v[0].size();
	v[use_machine({0,2})].push_back(2);
	if(n == 3)return v[0].size();
	int i1,i2;*/
	int ans = 0;
	bool f;

	int sq = min(n-1,130);
	int m= 1;
	
	for(int i = 1; i+k-2 < sq; i+=k-1){
		vector<bitset<k>> b;
		for(int j = 0; j < (1<<k); j+=2){
			bitset<k> bb = j;
			b.push_back(bb);
		}
		bitset<(1<<(k-1))>pos;for(int i = 0; i < 1<<(k-1); i++)pos[i]=1;
		vi ind = {0}; for(int j = i; j < i+k-1; j++)ind.push_back(j);
		while(pos.count()>1){
			vi vec;
			vi r;
			for(int j = 0; j < k; j++)if(rand()%2)r.push_back(j);
			for(int i : r)vec.push_back(ind[i]);
			int c = use_machine(vec);
			for(int j = 0; j < (1<<(k-1)); j++){
				int cc = 0;
				for(int t= 0; t < vec.size()-1; t++){
					cc+=(b[j][r[t]]^b[j][r[t+1]]);
				}
				if(cc!=c)pos[j]=0;
			}
		}
		for(int j = 0; j < (1<<(k-1)); j++){
			if(pos[j]){
				for(int t=  1; t < k; t++){
					v[(b[j][t])].push_back(ind[t]);
				}
			}
		}
		m = i+k-1;
	}

	ans = v[0].size();
	f = (v[1].size() > v[0].size());
	int s = v[f].size();
	for(int i = m; i < n; i+=s){
		int j = min(n-1, i+s-1);
		vi q;
		for(int k = i; k <= j; k++){
			q.push_back(k);
			q.push_back(v[f][k-i]);
		}
		int c = use_machine(q);
		if(!f){
			ans += q.size()/2;
			ans -= (c/2);
			ans -= (c%2);
		}else{
			ans += c/2;
			ans+=c%2;
		}
	}
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int t= 0; t < vec.size()-1; t++){
      |                   ~~^~~~~~~~~~~~~~

• Subtask 1: 48.8121 / 100