Submission #1302078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302078		opeleklanos	Counting Mushrooms (IOI20_mushrooms)	C++20	53.81 / 100	5 ms	428 KiB

mushrooms

#include <iostream>
#include <vector>
#include <math.h>
#include "mushrooms.h"
using namespace std;

// bool ans[] = {1, 0, 1, 1, 0, 1, 0, 1, 0};

// int use_machine(vector<int> v){
//     int curr = ans[v[0]];
//     int a = 0;
//     for(int i = 1; i<v.size(); i++){
//         if(ans[v[i]] != curr) a++;
//         curr = ans[v[i]];
//     }
//     return a;
// }


int count_mushrooms(int n){
    int ans = 1;
    vector<int> a = {0};
    vector<int> b;
    int rt = sqrt(n);
    int ind = 0;
    int res = 1;
    while(a.size() < rt && b.size() < rt){
        ind++;
        int tmp = use_machine({0, ind});
        if(tmp == 1) b.push_back(ind);
        else {a.push_back(ind); res++;}
    }
    char g = (a.size() > b.size())? 'a' : 'b';
    vector<int> good = (a.size() > b.size())? a : b;
    while(ind < n-1){
        int k = 0;
        vector<int> q;
        while(ind < n-1 && k<good.size()){
            if(q.size()%2){
                q.push_back(good[k++]);
            }
            else{
                q.push_back(++ind);
            }
        }
        if(ind == n-1) q.push_back(good[k++]);
        if(g == 'a'){
            res += q.size()/2 - ((use_machine(q)+1)/2);
        }
        else{
            res  += (use_machine(q) + 1) /2;
        }
    }
    return res;
}

// int main(void){
//     cout<<count_mushrooms(9);
// }


/*

a x a x a

4 ->

*/

• Subtask 1: 53.8095 / 100