Submission #827292

#	Time	Username	Problem	Language	Result	Execution time	Memory
827292		Amylopectin	Counting Mushrooms (IOI20_mushrooms)	C++14	89.68 / 100	471 ms	668 KiB

mushrooms

#include "mushrooms.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int mxn = 1e5 + 10,bo = 130;
int ta[2][mxn] = {},nu[mxn] = {},u[mxn] = {};
vector<int> fa;
int count_mushrooms(int n) 
{
	int i,j,cn,cm,fn,fm,co[2] = {1,0},cru = 1,cou,cva,us,ans = 0,fi;
	srand(time(0));
	ta[0][0] = 0;
	u[0] = 1;
	nu[0] = 0;
	for(i=1; i<n; i++)
	{
		cn = rand() % (n-i);
		cou = 0;
		for(j=0; j<n; j++)
		{
			if(u[j] == 0)
			{
				if(cou == cn)
				{
					nu[i] = j;
					u[j] = 1;
					break;
				}
				else 
				{
					cou ++;
				}
			}
		}
	}
	if(n == 1)
	{
		return 1;
	}
	if(n - cru == 1)
		{
			fa.clear();
			fa.push_back(nu[cru]);
			fa.push_back(0);
			cva = use_machine(fa);
			if(cva == 0)
			{
				ta[0][co[0]] = nu[cru];
				co[0] ++;
			}
			else 
			{
				ta[1][co[1]] = nu[cru];
				co[1] ++;
			}
			cru ++;
			return co[0];
		}
	fa.clear();
		fa.push_back(nu[cru]);
		fa.push_back(0);
		fa.push_back(nu[cru+1]);
		cva = use_machine(fa);
		if(cva == 0)
		{
			ta[0][co[0]] = nu[cru];
			ta[0][co[0] + 1] = nu[cru + 1];
			co[0] += 2;
		}
		else if(cva == 2)
		{
			ta[1][co[1]] = nu[cru];
			ta[1][co[1] + 1] = nu[cru + 1];
			co[1] += 2;
		}
		else 
		{
			fa.pop_back();
			cva = use_machine(fa);
			if(cva == 0)
			{
				ta[0][co[0]] = nu[cru];
				ta[1][co[1]] = nu[cru+1];
				co[0] ++;
				co[1] ++;
			}
			else 
			{
				ta[0][co[0]] = nu[cru+1];
				ta[1][co[1]] = nu[cru];
				co[0] ++;
				co[1] ++;
			}
		}
		cru += 2;
	// for(i=0; i<n; i++)
	// {
	// 	printf("%d ",nu[i]);
	// }

	while(cru < n)
	{
		if(n - cru == 1)
		{
			fa.clear();
			fa.push_back(nu[cru]);
			fa.push_back(0);
			cva = use_machine(fa);
			if(cva == 0)
			{
				ta[0][co[0]] = nu[cru];
				co[0] ++;
			}
			else 
			{
				ta[1][co[1]] = nu[cru];
				co[1] ++;
			}
			cru ++;
			break;
		}
		if(co[0] >= 2)
		{
			fa.clear();
			fa.push_back(nu[cru]);
			fa.push_back(ta[0][0]);
			fa.push_back(nu[cru+1]);
			fa.push_back(ta[0][1]);
			cva = use_machine(fa);
			if(cva == 0)
			{
				ta[0][co[0]] = nu[cru];
				ta[0][co[0] + 1] = nu[cru + 1];
				co[0] += 2;
			}
			else if(cva == 1)
			{
				ta[0][co[0]] = nu[cru+1];
				ta[1][co[1]] = nu[cru];
				co[0] ++;
				co[1] ++;
			}
			else if(cva == 2)
			{
				ta[0][co[0]] = nu[cru];
				ta[1][co[1]] = nu[cru+1];
				co[0] ++;
				co[1] ++;
			}
			else 
			{
				ta[1][co[1]] = nu[cru];
				ta[1][co[1] + 1] = nu[cru + 1];
				co[1] += 2;
			}
		}
		else 
		{
			fa.clear();
			fa.push_back(nu[cru]);
			fa.push_back(ta[1][0]);
			fa.push_back(nu[cru+1]);
			fa.push_back(ta[1][1]);
			cva = use_machine(fa);
			if(cva == 0)
			{
				ta[1][co[1]] = nu[cru];
				ta[1][co[1] + 1] = nu[cru + 1];
				co[1] += 2;
			}
			else if(cva == 1)
			{
				ta[0][co[0]] = nu[cru];
				ta[1][co[1]] = nu[cru+1];
				co[0] ++;
				co[1] ++;
			}
			else if(cva == 2)
			{
				ta[0][co[0]] = nu[cru+1];
				ta[1][co[1]] = nu[cru];
				co[0] ++;
				co[1] ++;
			}
			else 
			{
				ta[0][co[0]] = nu[cru];
				ta[0][co[0] + 1] = nu[cru + 1];
				co[0] += 2;
			}
		}
		// fa.clear();
		// fa.push_back(nu[cru]);
		// fa.push_back(0);
		// fa.push_back(nu[cru+1]);
		// cva = use_machine(fa);
		// if(cva == 0)
		// {
		// 	ta[0][co[0]] = nu[cru];
		// 	ta[0][co[0] + 1] = nu[cru + 1];
		// 	co[0] += 2;
		// }
		// else if(cva == 2)
		// {
		// 	ta[1][co[1]] = nu[cru];
		// 	ta[1][co[1] + 1] = nu[cru + 1];
		// 	co[1] += 2;
		// }
		// else 
		// {
		// 	fa.pop_back();
		// 	cva = use_machine(fa);
		// 	if(cva == 0)
		// 	{
		// 		ta[0][co[0]] = nu[cru];
		// 		ta[1][co[1]] = nu[cru+1];
		// 		co[0] ++;
		// 		co[1] ++;
		// 	}
		// 	else 
		// 	{
		// 		ta[0][co[0]] = nu[cru+1];
		// 		ta[1][co[1]] = nu[cru];
		// 		co[0] ++;
		// 		co[1] ++;
		// 	}
		// }
		cru += 2;
		if(co[0] >= bo || co[1] >= bo)
		{
			if(co[0] >= bo)
			{
				us = 0;
			}
			else 
			{
				us = 1;
			}
			break;
		}
	}
	ans = co[0];
	while(cru < n)
	{
		fa.clear();
		cou = 0;
		if(co[0] > co[1])
		{
			us = 0;
		}
		else 
		{
			us = 1;
		}
		for(i=0; i<co[us]; i++)
		{
			if(cru < n)
			{
				cou ++;
				if(i == 0)
				{
					fi = nu[cru];
				}
				fa.push_back(nu[cru]);
				cru ++;
			}
			fa.push_back(ta[us][i]);
		}
		cva = use_machine(fa);
		if(us == 0)
		{
			if(cva % 2 == 0)
			{
				ans ++;
				ta[0][co[0]] = fi;
				co[0] ++;
			}
			else 
			{
				ta[1][co[1]] = fi;
				co[1] ++;
			}
			ans += cou - 1 - (cva/2);
		}
		else 
		{
			if(cva % 2 == 1)
			{
				ans ++;
				ta[0][co[0]] = fi;
				co[0] ++;
			}
			else 
			{
				ta[1][co[1]] = fi;
				co[1] ++;
			}
			ans += cva/2;
		}
	}
	return ans;
	// std::vector<int> m;
	// for (int i = 0; i < n; i++)
	// 	m.push_back(i);
	// int c1 = use_machine(m);
	// m = {0, 1};
	// int c2 = use_machine(m);
	// return c1+c2;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:13:13: warning: unused variable 'cm' [-Wunused-variable]
   13 |  int i,j,cn,cm,fn,fm,co[2] = {1,0},cru = 1,cou,cva,us,ans = 0,fi;
      |             ^~
mushrooms.cpp:13:16: warning: unused variable 'fn' [-Wunused-variable]
   13 |  int i,j,cn,cm,fn,fm,co[2] = {1,0},cru = 1,cou,cva,us,ans = 0,fi;
      |                ^~
mushrooms.cpp:13:19: warning: unused variable 'fm' [-Wunused-variable]
   13 |  int i,j,cn,cm,fn,fm,co[2] = {1,0},cru = 1,cou,cva,us,ans = 0,fi;
      |                   ^~
mushrooms.cpp:278:18: warning: 'fi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  278 |     ta[0][co[0]] = fi;
      |     ~~~~~~~~~~~~~^~~~

• Subtask 1: 89.6825 / 100