oj.uz

Submission #829724

# Submission time Handle Problem Language Result Execution time Memory
829724 2023-08-18T14:28:49 Z minhcool Counting Mushrooms (IOI20_mushrooms) C++17
100 / 100
 7 ms 336 KB 
#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, 100);
	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 - 2, 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]);
            v.pb(nxt + 1);
			int temp = use_machine(v);
			answer += (v.size() - 1 - temp)/2;
            if(temp & 1) v2.pb(nxt + 1);
            else{
              	v1.pb(nxt + 1);
                answer++;
			}
			itr = nxt + 2;
			//cout << answer << "\n";
		}
		else{
			int nxt = min(n - 2, 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]);
            v.pb(nxt + 1);
			int temp = use_machine(v);
			answer += temp/2;
            if(temp & 1){
            	v1.pb(nxt + 1);
                answer++;
            }
            else v2.pb(nxt + 1);
			itr = nxt + 2;
		}
	}
	return answer;
}

Compilation message

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:167:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |             assert((nxt - itr + 1) < v2.size());
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 6 ms 208 KB Output is correct
8 Correct 4 ms 308 KB Output is correct
9 Correct 4 ms 208 KB Output is correct
10 Correct 4 ms 208 KB Output is correct
11 Correct 5 ms 208 KB Output is correct
12 Correct 6 ms 208 KB Output is correct
13 Correct 6 ms 316 KB Output is correct
14 Correct 3 ms 324 KB Output is correct
15 Correct 5 ms 208 KB Output is correct
16 Correct 5 ms 208 KB Output is correct
17 Correct 3 ms 308 KB Output is correct
18 Correct 6 ms 208 KB Output is correct
19 Correct 5 ms 316 KB Output is correct
20 Correct 6 ms 312 KB Output is correct
21 Correct 5 ms 208 KB Output is correct
22 Correct 5 ms 208 KB Output is correct
23 Correct 4 ms 308 KB Output is correct
24 Correct 3 ms 208 KB Output is correct
25 Correct 5 ms 328 KB Output is correct
26 Correct 7 ms 328 KB Output is correct
27 Correct 5 ms 320 KB Output is correct
28 Correct 7 ms 328 KB Output is correct
29 Correct 5 ms 336 KB Output is correct
30 Correct 6 ms 324 KB Output is correct
31 Correct 6 ms 208 KB Output is correct
32 Correct 5 ms 324 KB Output is correct
33 Correct 5 ms 324 KB Output is correct
34 Correct 6 ms 208 KB Output is correct
35 Correct 5 ms 208 KB Output is correct
36 Correct 4 ms 332 KB Output is correct
37 Correct 7 ms 300 KB Output is correct
38 Correct 5 ms 208 KB Output is correct
39 Correct 6 ms 316 KB Output is correct
40 Correct 7 ms 208 KB Output is correct
41 Correct 5 ms 208 KB Output is correct
42 Correct 4 ms 308 KB Output is correct
43 Correct 7 ms 324 KB Output is correct
44 Correct 5 ms 320 KB Output is correct
45 Correct 5 ms 208 KB Output is correct
46 Correct 4 ms 312 KB Output is correct
47 Correct 5 ms 208 KB Output is correct
48 Correct 7 ms 208 KB Output is correct
49 Correct 4 ms 324 KB Output is correct
50 Correct 6 ms 300 KB Output is correct
51 Correct 5 ms 208 KB Output is correct
52 Correct 6 ms 316 KB Output is correct
53 Correct 5 ms 316 KB Output is correct
54 Correct 4 ms 208 KB Output is correct
55 Correct 6 ms 320 KB Output is correct
56 Correct 5 ms 208 KB Output is correct
57 Correct 7 ms 208 KB Output is correct
58 Correct 7 ms 208 KB Output is correct
59 Correct 5 ms 208 KB Output is correct
60 Correct 5 ms 328 KB Output is correct
61 Correct 6 ms 308 KB Output is correct
62 Correct 1 ms 208 KB Output is correct
63 Correct 1 ms 208 KB Output is correct
64 Correct 1 ms 208 KB Output is correct
65 Correct 1 ms 208 KB Output is correct
66 Correct 0 ms 208 KB Output is correct
67 Correct 0 ms 208 KB Output is correct
68 Correct 0 ms 208 KB Output is correct
69 Correct 0 ms 208 KB Output is correct
70 Correct 0 ms 208 KB Output is correct
71 Correct 0 ms 208 KB Output is correct
72 Correct 0 ms 208 KB Output is correct
73 Correct 1 ms 208 KB Output is correct
74 Correct 0 ms 208 KB Output is correct
75 Correct 0 ms 208 KB Output is correct
76 Correct 0 ms 208 KB Output is correct
77 Correct 0 ms 208 KB Output is correct
78 Correct 0 ms 208 KB Output is correct
79 Correct 0 ms 208 KB Output is correct
80 Correct 0 ms 208 KB Output is correct
81 Correct 0 ms 208 KB Output is correct
82 Correct 0 ms 208 KB Output is correct
83 Correct 0 ms 208 KB Output is correct
84 Correct 0 ms 208 KB Output is correct
85 Correct 0 ms 208 KB Output is correct
86 Correct 0 ms 208 KB Output is correct
87 Correct 0 ms 208 KB Output is correct
88 Correct 0 ms 208 KB Output is correct
89 Correct 0 ms 208 KB Output is correct
90 Correct 0 ms 208 KB Output is correct
91 Correct 0 ms 208 KB Output is correct