Submission #827313

#	Time	Username	Problem	Language	Result	Execution time	Memory
827313		ttamx	Counting Mushrooms (IOI20_mushrooms)	C++14	92.62 / 100	8 ms	532 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>

using namespace std;

const int CUT=77;

int count_mushrooms(int n) {
	if(n==2)return 2-use_machine({0,1});
	vector<int> c(n);
	c[0]=0;
	vector<int> pos[2];
	for(int i=1;i<=2;i++)c[i]=use_machine({0,i});
	for(int i=0;i<=2;i++)pos[c[i]].emplace_back(i);
	int id=pos[1].size()>pos[0].size();
	int front=3;
	for(int i=0;i<CUT&&front+1<n;i++,front+=2){
		int tmp=use_machine({front,pos[id][0],front+1,pos[id][1]});
		c[front]=tmp&1^id;
		c[front+1]=tmp>>1^id;
		pos[c[front]].emplace_back(front);
		pos[c[front+1]].emplace_back(front+1);
	}
	int last=n;
	int sum=0;
	for(int i=front;i<last;i++){
		id=pos[1].size()>pos[0].size();
		vector<int> res;
		int cnt=0;
		for(int j=0;j<pos[id].size();j++){
			if(j==0){
				res.emplace_back(i);
			}else{
				res.emplace_back(--last);
				cnt++;
			}
			res.emplace_back(pos[id][j]);
			if(last==i+1)break;
		}
		int tmp=use_machine(res);
		c[i]=tmp&1^id;
		pos[c[i]].emplace_back(i);
		if(id){
			sum+=tmp>>1;
		}else{
			sum+=cnt-(tmp>>1);
		}
	}
	for(int i=0;i<last;i++)sum+=c[i]==0;
	return sum;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:19:15: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   19 |   c[front]=tmp&1^id;
      |            ~~~^~
mushrooms.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int j=0;j<pos[id].size();j++){
      |               ~^~~~~~~~~~~~~~~
mushrooms.cpp:41:11: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   41 |   c[i]=tmp&1^id;
      |        ~~~^~

• Subtask 1: 92.623 / 100