Submission #828768

#	Time	Username	Problem	Language	Result	Execution time	Memory
828768		minhcool	Counting Mushrooms (IOI20_mushrooms)	C++17	88.98 / 100	7 ms	424 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;
}
 
vector<int> mp[10];
 
void prep(){
	for(int i = 0; i < (1LL << 9); i++){
		vector<int> v;
		for(int j = 0; j < 9; j++) v.pb((i & (1LL << j)) != 0);
		if(!v[0] || !v[2] || v[3] || v[5] || v[7]) continue;
		if(v[1] == v[4]) continue;
		int tot = 0;
		for(int j = 0; j < 8; j++) tot += (v[j] != v[j + 1]);
		//assert(!mp[tot].size());
		//cout << tot << "\n";
		//for(int j = 0; j < 9; j++) cout << v[j] << " ";
		//cout << "\n";
		mp[tot] = v; 
	}
	//for(int i = 1; i <= 8; i++) assert(mp[i].size());
}
 
int count_mushrooms(int n){
	if(n <= 200){
		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;
	}
    int lim = min(n / 3, 170);
	prep();
	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() < lim && v2.size() < lim){
		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;
		if(v1.size() >= 3 && v2.size() >= 3) break;
	}
	itr++;
	//cout << itr << " " << v1.size() << " " << v2.size() << "\n";
	while(v1.size() < lim && v2.size() < lim){
		vector<int> v;
		v.pb(v1[0]);
		v.pb(itr);
		v.pb(v1[1]);
		v.pb(itr + 1);
		v.pb(v1[2]);
		v.pb(itr + 2);
		int temp = use_machine(v);
		//cout << temp << " " << v1.size() << " " << v2.size() << " " << "\n";
		if(temp <= 1){
			v1.pb(itr), v1.pb(itr + 1);
			if(temp == 1) v2.pb(itr + 2);
			else v1.pb(itr + 2);
			itr += 3;
			continue;
		}
		if(temp >= 4){
			v2.pb(itr), v2.pb(itr + 1);
			if(temp == 4) v1.pb(itr + 2);
			else v2.pb(itr + 2);
			itr += 3;
			continue;
		}
		if(temp == 2) v1.pb(itr + 2);
		else v2.pb(itr + 2);
		v.clear();
		v.pb(v2[0]), v.pb(itr), v.pb(v2[1]), v.pb(v1[0]), v.pb(itr + 1), v.pb(v1[1]), v.pb(itr + 3), v.pb(v1[2]), v.pb(itr + 4);
		temp = use_machine(v);
		vector<int> vv = mp[temp];
		if(!vv[1]) v1.pb(itr);
		else v2.pb(itr);
		if(!vv[4]) v1.pb(itr + 1);
		else v2.pb(itr + 1);
		if(!vv[6]) v1.pb(itr + 3);
		else v2.pb(itr + 3);
		if(!vv[8]) v1.pb(itr + 4);
		else v2.pb(itr + 4);
		itr += 5;
		//cout << itr << " " << v1.size() << " " << v2.size() << "\n";
	}
	//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;
			//cout << answer << "\n";
		}
		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;
      |                ~~~~~^~~
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:74:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |  while(v1.size() < lim && v2.size() < lim){
      |        ~~~~~~~~~~^~~~~
mushrooms.cpp:74:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |  while(v1.size() < lim && v2.size() < lim){
      |                           ~~~~~~~~~~^~~~~
mushrooms.cpp:97:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |  while(v1.size() < lim && v2.size() < lim){
      |        ~~~~~~~~~~^~~~~
mushrooms.cpp:97:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |  while(v1.size() < lim && v2.size() < lim){
      |                           ~~~~~~~~~~^~~~~
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:148:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |             assert((nxt - itr + 1) < v1.size());
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:161:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |             assert((nxt - itr + 1) < v2.size());
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 88.9764 / 100