Submission #406569

#	Time	Username	Problem	Language	Result	Execution time	Memory
406569		AmineTrabelsi	Counting Mushrooms (IOI20_mushrooms)	C++14	10 / 100	174 ms	292 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
	int ans = 1;
    int a = -1;
    int ind = 1;
    for(int i=1;i+9<n;i+=10){
        vector<int> m;
        for(int j=0;j<10;j++){
            m.push_back(i+j);
        }
        int cnt = use_machine(m);
        if(cnt == 0){
            vector<int> t;
            t.push_back(0);
            for(int j=0;j<(int)m.size();j++){
                t.push_back(m[j]);
            }
            int n_cnt = use_machine(t);
            if(n_cnt == 0){
                ans += 10;
                a = i;
            }
        }else{
            for(int j=0;j<(int)m.size();j++){
                if(use_machine({0,m[j]}) == 0){
                    a = m[j];
                    ans++;
                }
            }
        }
        ind = i+10;
        if(a != -1)break;
    }
    if(a != -1){
        for(int i=ind;i+2<n;i+=3){
            vector<int> m = {i,i+1,i+2};
            int cnt = use_machine(m);
            if(cnt == 0){
                m.push_back(0);
                int ncnt = use_machine(m);
                if(ncnt == 0)ans += 3;
            }else if(cnt == 2){
                m.push_back(0);
                int ncnt = use_machine(m);
                if(ncnt == 2)ans += 2;
                else ans++;
            }else{
                // 1
                m = {i,0,i+1,a,i+2};
                int ncnt = use_machine(m);
                if(ncnt == 1)ans += 2;
                else ans++;
            }
            ind = i+3;
        }
    }
    while(ind < n){
        ans += use_machine({0,ind++}) == 0;
    }
	return ans;
}
/*
-> one op needed
AAA : 0
BBB : 0
-> one op also
add after the first and before the last
AAB : 1
BAA : 1

ABB : 1
BBA : 1

-> one op needed
ABAA : 2
BABA : 2
*/

• Subtask 1: 10 / 100