Submission #1174781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174781		khanhphucscratch	Counting Mushrooms (IOI20_mushrooms)	C++20	56.78 / 100	3 ms	428 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int an[20005];
/*int use_machine(vector<int> s)
{
    int ans = 0;
    for(int i = 1; i < s.size(); i++) ans += (an[s[i]] != an[s[i-1]]);
    return ans;
}*/
int count_mushrooms(int n)
{
    int ans = 1;
    if(n <= 200){
        for(int i = 1; i < n; i++) ans += 1-use_machine({0, i});
        return ans;
    }
    vector<int> a, b;
    a.push_back(0);
    for(int i = 1; i <= 200; i++){
        if(use_machine({0, i}) == 1) b.push_back(i);
        else{
            a.push_back(i);
            ans++;
        }
    }
    if(a.size() > 100){
        int p = 201;
        while(p < n){
            vector<int> truncate = {a[0]};
            int add = 0;
            for(int i = 1; i < a.size(); i++){
                if(p == n) break;
                truncate.push_back(p++);
                truncate.push_back(a[i]);
                add++;
            }
            ans += add - use_machine(truncate)/2;
        }
    }
    else{
        int p = 201;
        while(p < n){
            vector<int> truncate = {b[0]};
            for(int i = 1; i < b.size(); i++){
                if(p == n) break;
                truncate.push_back(p++);
                truncate.push_back(b[i]);
            }
            ans += use_machine(truncate)/2;
        }
    }
    return ans;
}
/*mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
signed main()
{
    int n, c = 0; cin>>n;
    for(int i = 0; i < n; i++){
        an[i] = rng()%2;
        if(i == 0) an[i] = 1;
        c += an[i];
    }
    cerr<<c<<" "<<count_mushrooms(n);
}*/

• Subtask 1: 56.7839 / 100