Submission #1326399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326399		opeleklanos	Counting Mushrooms (IOI20_mushrooms)	C++20	80.71 / 100	3 ms	448 KiB

mushrooms

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

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

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


int count_mushrooms(int n){
    vector<int> aIndx [2] = {{0}, {}};
    int r = 1;
    int c = 1;
    while(r<n){
        vector<int> newUse;
        int mx =aIndx[0].size()>aIndx[1].size()?0:1;
        int oldR = r;
        for(int i = 0; i<aIndx[mx].size(); i++){
            if(r>=n) break;
            newUse.push_back(r);
            newUse.push_back(aIndx[mx][i]);
            r++;
        }
        int ans = use_machine(newUse);
        if(((ans % 2 == 1) && (mx == 1)) || ((ans%2 == 0) && mx == 0)) {aIndx[0].push_back(oldR); c++;}
        else aIndx[1].push_back(oldR);

        if(mx == 0) c += ((newUse.size()-2)/2) - ans/2;
        else c += ans/2;
    }
    return c;
}

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

• Subtask 1: 80.7143 / 100