Submission #759910

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

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

int count_mushrooms(int n) {
// 	std::vector<int> m;
// 	for (int i = 0; i < n; i++)
// 		m.push_back(i);
// 	int c1 = use_machine(m);
// 	m = {0, 1};
// 	int c2 = use_machine(m);
// 	return c1+c2;

    vector <int> a, b;
    a.push_back(0);
    int N = min(200, n);
    
    for (int i = 1; i < N; i++){
        vector <int> m = {0, i};
        int c = use_machine(m);
        
        if (c == 0) a.push_back(i);
        else b.push_back(i);
    }
    
    if (N == n) return a.size();
    int ans = 0;
    
    while (N < n){
        int x = min(N + 99, n - 1);
        int add = x - N + 1;
        
        if (a.size() >= 100){
            vector <int> m;
            for (int i = 0; i < add; i++){
                m.push_back(a[i]);
                m.push_back(N + i);
            }
            
            int c = use_machine(m);
            //every B will add 2, except for 1 
            c++;
            int bb = c/2;
            int aa = add - bb;
            ans += aa;
        } else {
            assert(b.size() >= 100);
            vector <int> m;
            for (int i = 0; i < add; i++){
                m.push_back(b[i]);
                m.push_back(N + i);
            }
            
            int c = use_machine(m) + 1;
            ans += c/2;
        }
        
        N = x + 1;
    }
    
    return ans;
}

• Subtask 1: 0 / 100