Submission #484955

#	Time	Username	Problem	Language	Result	Execution time	Memory
484955		MohamedFaresNebili	Counting Mushrooms (IOI20_mushrooms)	C++14	56.93 / 100	14 ms	360 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
 
        using namespace std;
 
        using ll  = long long;
        using vi  = vector<int>;
 
        #define pb push_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define all(x) (x).begin() , (x).end()
        
 
        //int use_machine(vector<int> a);
 
        int count_mushrooms(int n) {
            int cnt = 1;
            int k = 200;
            vector<int>arrA, arrB;
            for(int i = 1;i<k && i<n;i++){
                vector<int> a;
                a = {0, i};
                if(use_machine(a)) arrB.pb(i);
                else arrA.pb(i), cnt++;
            }
            #define sz(x) (int)x.size()
            if(sz(arrA) >= sz(arrB)) {
                int i = k;
                while(i<n){
                    vector<int> a;
                    for(int j : arrA){
                        a.pb(j);
                        a.pb(i);
                        i++;
                        if(i == n)break;
                    }
                    int x = use_machine(a);
                    cnt += (int)a.size()/2 - (x+1)/2;
                }
            }
            else {
                int i = k;
                while(i<n){
                    vector<int> b;
                    for(int j : arrB){
                        b.pb(j);
                        b.pb(i);
                        i++;
                        if(i == n)break;
                    }
                    int x = use_machine(b);
                    cnt += (x+1)/2;
                }
            }
            return cnt;
        
        }

• Subtask 1: 56.927 / 100