Submission #592313

#	Time	Username	Problem	Language	Result	Execution time	Memory
592313		farhan132	Counting Mushrooms (IOI20_mushrooms)	C++17	25.17 / 100	18 ms	384 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 <= 100){
		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);
	for(ll i = 1; i <= 101; 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 = 102; 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);
		}
	}
	for(ll i = 1; i < n; i++){
		if(!done[i]) ans += 1 - use_machine({0, i});
	}
	
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:38:28: warning: unused variable 'q' [-Wunused-variable]
   38 |    cur.pb(A[0]); ll p = i, q = 1;
      |                            ^
mushrooms.cpp:49:28: warning: unused variable 'q' [-Wunused-variable]
   49 |    cur.pb(B[0]); ll p = i, q = 1;
      |                            ^

• Subtask 1: 25.167 / 100