Submission #620739

#	Time	Username	Problem	Language	Result	Execution time	Memory
620739		wiwiho	Counting Mushrooms (IOI20_mushrooms)	C++14	56.93 / 100	12 ms	312 KiB

mushrooms

#include "mushrooms.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int count_mushrooms(int n) {
    
    int K = min(n, 200);

    int sum = 0;

    vector<int> red, blue;
    red.eb(0);
    for(int i = 1; i < K; i++){
        vector<int> tmp = {0, i};
        sum += 2;
        if(use_machine(tmp) == 1) blue.eb(i);
        else red.eb(i);
    }

    bool f = false;
    if(red.size() < blue.size()){
        red.swap(blue);
        f = true;
    }

    int cnt = red.size();
    //cerr << "cnt " << cnt << "\n";
    for(int i = K; i < n; i += (int)red.size()){
        vector<int> tmp;
        int total = 0;
        for(int j = 0; i + j < n && j < (int) red.size(); j++){
            tmp.eb(red[j]);
            tmp.eb(i + j);
            total++;
        }
        sum += tmp.size();
        //cerr << "use " << total << " " << tmp.size() << " " << sum << "\n";
        int r = use_machine(tmp);
        int diff = (r + 1) / 2;
        cnt += total - diff;
    }
    
    if(f) cnt = n - cnt;
    return cnt;
}

• Subtask 1: 56.927 / 100