Submission #1005242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005242		PenguinsAreCute	Counting Mushrooms (IOI20_mushrooms)	C++17	53.30 / 100	7 ms	448 KiB

mushrooms

    #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={A[0]};}
    		}
    	} 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={B[0]};}
    		}
    	}
    	return ans;
    }

• Subtask 1: 53.3019 / 100