oj.uz

Submission #1005230

# Submission time Handle Problem Language Result Execution time Memory
1005230 2024-06-22T09:08:43 Z PenguinsAreCute Counting Mushrooms (IOI20_mushrooms) C++17
0 / 100
 1 ms 344 KB 
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int HSQ = 70;
int THSQ = 2*HSQ+1;
int count_mushrooms(int n) {
	if(n<=140) {
		int ans = 1;
		for(int i=1;i<n;i++) ans += !use_machine({0,i});
		return ans;
	}
	bool st[THSQ]; st[0]=1;
	for(int i=1;i<THSQ;i++) st[i]=!use_machine({0,i});
	vector<int> A, B;
	for(int i=0;i<THSQ;i++) {
		if(st[i]) A.push_back(i);
		else B.push_back(i);
	}
	int ans = A.size();
	if(A.size()>B.size()) {
		vector<int> v={A[0]};
		for(int j=THSQ;j<n;j++) {
			v.push_back(j);
			v.push_back(A[((j-1)%HSQ)+1]);
			if(j==n-1||(!(j%HSQ))) {ans += (v.size()-1-use_machine(v))/2; v.clear();}
		}
	} else {
		vector<int> v={B[0]};
		for(int j=THSQ;j<n;j++) {
			v.push_back(j);
			v.push_back(B[((j-1)%HSQ)+1]);
			if(j==n-1||!(j%HSQ)) {ans += use_machine(v)/2; v.clear();}
		}
	}
	return ans;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 1 ms 344 KB Answer is not correct.
7 Halted 0 ms 0 KB -