Submission #1302257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302257		opeleklanos	Counting Mushrooms (IOI20_mushrooms)	C++20	80.43 / 100	4 ms	452 KiB

mushrooms

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

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

// 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 res = 0;
    vector<int> a = {0};
    vector<int> b;
    int indL = 0, indR = n;
    while(indL < indR-1){
        indL++;
        vector<int> q = {indL};
        for(int i = 0; (i<max(a.size(), b.size())) && (indR>1+indL); i++){
            q.push_back(a.size()>b.size()?a[i]:b[i]);
            q.push_back(--indR);
        }

        if(q.size() == 1) q.push_back(a.size()>b.size()?a[0]:b[0]);
        else if(q.size()%2){
            q.pop_back();
            indR++;
        }

        int tmp = use_machine(q);
        if(a.size() <= b.size()) res += tmp/2;
        else res += (q.size()/2 - 1) - (tmp/2);

        if((b.size() < a.size()) && (tmp%2 == 0)) a.push_back(indL);
        else if((b.size() < a.size()) && (tmp%2 == 1)) b.push_back(indL); 
        else if((b.size() >= a.size()) && (tmp%2 == 1)) a.push_back(indL);
        else if((b.size() >= a.size()) && (tmp%2 == 0)) b.push_back(indL);
        //if(tmp%2 == 1) tmp--;
    }
    return res + a.size();
}

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


/*

a x a x a

4 ->

*/

• Subtask 1: 80.427 / 100