Submission #759940

#	Time	Username	Problem	Language	Result	Execution time	Memory
759940		raysh07	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	0 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;

    // if (n <= 5000){
    // 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 + a.size();
    // }
    
    vector <int> a, b;
    a.push_back(0);
    int p = 1;
    int ans = 0;
    
    while (p < n){
        if (a.size() > b.size()){
            int g = a.size();
            g = min(g, n - p);
            
            vector <int> m;
            for (int i = 0; i < g; i++){
                m.push_back(p + i);
                m.push_back(a[i]);
            }
            
            int c = use_machine(m);
            if (c & 1) b.push_back(p), c--;
            else a.push_back(p);
            
            ans += g - c/2;
            p += g;
        } else {
            int g = b.size();
            g = min(g, n - p);
            
            vector <int> m;
            for (int i = 0; i < g; i++){
                m.push_back(p + i);
                m.push_back(b[i]);
            }
            
            int c = use_machine(m);
            if (c & 1) a.push_back(p), c--;
            else b.push_back(p);
            
            ans += c/2;
            p += g;
        }
    }
    
    return ans + a.size();
}

• Subtask 1: 0 / 100