Submission #592321

#	Time	Username	Problem	Language	Result	Execution time	Memory
592321		farhan132	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	2 ms	208 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

int count_mushrooms(int n) {
	ll ans = 1;
	
	if(n <= 150){
		for(ll i = 1; i < n; i++){
			ans += 1 - use_machine({0, i});
		}
		return ans;
	}

	vector < ll > done(n + 100, 0);
	vector < ll > A, B;
	A.pb(0);
	ll N = 141;
	for(ll i = 1; i <= N; i++){
		if(1 - use_machine({0, i})) A.pb(i), ans++;
		else B.pb(i);
		done[i] = 1;
	}
	ll sz; bool f = 0;
	if(B.size() > A.size()) f = 1, sz = B.size();
	else sz = A.size();
	for(ll i = N + 1; i + sz - 1 < n; i+=sz){
		if(!f){
			vector < ll > cur;
			cur.pb(A[0]); ll p = i, q = 1;
			for(ll j = 1; j < sz; j++){
				done[p] = 1;
				cur.pb(p);
				cur.pb(A[j]);
				p++;
			}
			ll k = use_machine(cur);
			ans += (sz - 1) - (k/2);
		}else{
			vector < ll > cur;
			cur.pb(B[0]); ll p = i, q = 1;
			for(ll j = 1; j < sz; j++){
				done[p] = 1;
				cur.pb(p);
				cur.pb(B[j]);
				p++;
			}
			ll k = use_machine(cur);
			ans += (k/2);
		}
	}
	vector < ll > all;
	for(ll i = 1; i < n; i++){
		if(!done[i]) all.pb(i);
	}
	if(all.size()){
	if(!f){
			vector < ll > cur;
			cur.pb(A[0]);
			for(ll j = 1; j <= all.size(); j++){
				cur.pb(all[j - 1]);
				cur.pb(A[j]);
			}
			ll k = use_machine(cur);
			ans += (sz - 1) - (k/2);
		}else{
			vector < ll > cur;
			cur.pb(B[0]);
			for(ll j = 1; j <= all.size(); j++){
				cur.pb(all[j - 1]);
				cur.pb(B[j]);
			}
			ll k = use_machine(cur);
			ans += (k/2);
	}
	}
	
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:39:28: warning: unused variable 'q' [-Wunused-variable]
   39 |    cur.pb(A[0]); ll p = i, q = 1;
      |                            ^
mushrooms.cpp:50:28: warning: unused variable 'q' [-Wunused-variable]
   50 |    cur.pb(B[0]); ll p = i, q = 1;
      |                            ^
mushrooms.cpp:69:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(ll j = 1; j <= all.size(); j++){
      |                  ~~^~~~~~~~~~~~~
mushrooms.cpp:78:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for(ll j = 1; j <= all.size(); j++){
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 100