Submission #828376

#	Time	Username	Problem	Language	Result	Execution time	Memory
828376		minhcool	Counting Mushrooms (IOI20_mushrooms)	C++17	80.14 / 100	8 ms	336 KiB

mushrooms

#include "mushrooms.h"
//#define local
#ifndef local
//#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int count_mushrooms(int n){
	if(n <= 280){
		int answer = 1;
		for(int i = 1; i < n; i++){
			vector<int> v;
			v.pb(0), v.pb(i);
			answer += (!use_machine(v)); 
		}
		return answer;
	}
	vector<int> v;
	v.pb(0), v.pb(1);
	vector<int> v1, v2;
	v1.pb(0);
	if(use_machine(v)) v2.pb(1);
	else v1.pb(1);
	v.clear();
	v.pb(0), v.pb(2);
	if(use_machine(v)) v2.pb(2);
	else v1.pb(2);
	int itr = 2;
	while(v1.size() < 141 && v2.size() < 141){
		vector<int> v;
		if(v1.size() >= 2){
			v.pb(v1[0]), v.pb(itr + 1), v.pb(v1[1]), v.pb(itr + 2);
			int temp = use_machine(v);
			if(temp & 1) v2.pb(itr + 2);
			else v1.pb(itr + 2);
			if(temp & 2) v2.pb(itr + 1);
			else v1.pb(itr + 1);
		}
		else{
			v.pb(v2[0]), v.pb(itr + 1), v.pb(v2[1]), v.pb(itr + 2);
			int temp = use_machine(v);
			if(temp & 1) v1.pb(itr + 2);
			else v2.pb(itr + 2);
			if(temp & 2) v1.pb(itr + 1);
			else v2.pb(itr + 1);
		}
		itr += 2;
	}
	itr++;
	int answer = v1.size();
  //return answer;
	while(itr < n){
		if(v1.size() >= v2.size()){
			int nxt = min(n - 1, itr + (int)v1.size() - 2);
			vector<int> v;
			for(int i = itr; i <= nxt; i++){
				v.pb(v1[i - itr]), v.pb(i);
			}
            assert((nxt - itr + 1) < v1.size());
			v.pb(v1[nxt - itr + 1]);
			int temp = use_machine(v);
          answer += (v.size() - 1 - temp)/2;
			itr = nxt + 1;
		}
		else{
			int nxt = min(n - 1, itr + (int)v2.size() - 2);
			vector<int> v;
			for(int i = itr; i <= nxt; i++){
				v.pb(v2[i - itr]), v.pb(i);
			}
            assert((nxt - itr + 1) < v2.size());
			v.pb(v2[nxt - itr + 1]);
			int temp = use_machine(v);
			answer += temp/2;			
			itr = nxt + 1;
		}
	}
	return answer;
}

Compilation message (stderr)

mushrooms.cpp:23:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from mushrooms.cpp:7:
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:83:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             assert((nxt - itr + 1) < v1.size());
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:95:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             assert((nxt - itr + 1) < v2.size());
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 80.1418 / 100