Submission #703828

#	Time	Username	Problem	Language	Result	Execution time	Memory
703828		n1k	Counting Mushrooms (IOI20_mushrooms)	C++17	Compilation error	0 ms	0 KiB

mushrooms

#include <bits/stdc++.h>

#define ll long long
#define vt vector
#define pb push_back
#define ar array
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()

using namespace std;

/*
 1. simplify
 2. add new elements
 3. brute force solution
 4. optimize
 5. start implementing
*/

// --- templates ---

vt<int> shrooms = {0, 1, 0, 1, 0, 1, 0};

int c = 0;

int use_machine(vt<int> x){
	c++;
	int n = sz(x);
	int ans = 0;
	for(int i = 1; i < n; i++){
		ans += shrooms[x[i - 1]] != shrooms[x[i]];
	}
	return ans;
}

// --- code ---


const int take = 144 * 2;

int count_mushrooms(int n){
	vt<vt<int>> shrom(2);

	shrom[0].pb(0);

	for(int i = 1; i < min(3, n); i++){
		shrom[use_machine({0, i})].pb(i);
	}

	vt<int> find(4);

	bool isb = shrom[1].size() >= 2;

	find[1] = shrom[isb][0];
	find[3] = shrom[isb][1];

	for(int i = 3; i < take + 3 && i < n; i+=2){
		if(i == n - 1){
			shrom[use_machine({0, i})].pb(i);
		}else{
			find[0] = i; find[2] = i + 1;
			int res = use_machine(find);
			
			shrom[(res & 1) ^ isb].pb(i);

			shrom[((res & 2) >> 1) ^ isb].pb(i + 1);	
		}
	}

	int cnta = sz(shrom[0]);

	for(int i = take + 3; i < n; i += sz(shrom[isb])){
		find.clear();
		for(int j = 0; j < sz(shrom[isb]) && i + j < n; j++){
			find.pb(shrom[isb][j]);
			find.pb(i + j);
		}
		int res = use_machine(find);
		if(isb){
			cnta += (res + 1) / 2;
		}else{
			cnta += sz(find) / 2 - (res + 1) / 2;
		}
	}

	return cnta;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int j = 0; j < sz(shrom[isb]) && i + j < n; j++){
      |                    ^
/usr/bin/ld: /tmp/ccLIPhad.o: in function `use_machine(std::vector<int, std::allocator<int> >)':
stub.cpp:(.text+0x150): multiple definition of `use_machine(std::vector<int, std::allocator<int> >)'; /tmp/ccQrcTMc.o:mushrooms.cpp:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status