Submission #599483

#	Time	Username	Problem	Language	Result	Execution time	Memory
599483		alontanay	Counting Mushrooms (IOI20_mushrooms)	C++14	80.71 / 100	10 ms	468 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"

using namespace std;

int count_mushrooms(int n) {
    if(n == 2) {
        return 2-use_machine({0,1});
    }
    bool swp = false;
	vector<int> as = {0};
    vector<int> bs;
    int res = 0;
    int idx = 0;
    while(idx < n - 1) {
        if(bs.size() > as.size()) {
            swp = !swp;
			swap(as,bs);
        }
        int sz = as.size();
        if(idx + sz >= n) {
            vector<int> m;
			for(int j = 0; idx < n - 1; j ++) {
				m.push_back(as[j]);
				m.push_back(++idx);
			}
			int x = use_machine(m);
			if(x&1) {
				bs.push_back(idx);
			} else {
				as.push_back(idx);
			}
			if(swp) {
				res += (x)/2;
			} else {
				res += ((m.size()/2) - 1)-(x)/2;
			}
			break;
        }
        vector<int> m;
        for(int j = 0; j < sz; j ++) {
            m.push_back(as[j]);
            m.push_back(++idx);
        }
        int x = use_machine(m);
        if(x&1) {
            bs.push_back(idx);
        } else {
            as.push_back(idx);
        }
        if(swp) {
            res += (x)/2;
        } else {
            res += ((m.size()/2) - 1)-(x)/2;
        }
    }
    return res + (swp?bs.size():as.size());
}

• Subtask 1: 80.7143 / 100