Submission #622915

#	Time	Username	Problem	Language	Result	Execution time	Memory
622915		sokratisi	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	2 ms	208 KiB

mushrooms

#include "mushrooms.h"
#include <vector>

using namespace std;

int count_mushrooms(int n) {
    if (n < 283) {
        int counta = 1;
        for (int i = 1; i < n; i++) {
            int re = use_machine({0, i});
            if (!re) counta++;
        }
        return counta;
    }
    vector<int> state(n, -1);
    state[0] = 0;
    int re;
    re = use_machine({0, 1});
    if (re) state[1] = 1;
    else state[1] = 0;
    re = use_machine({0, 2});
    if (re) state[2] = 1;
    else state[2] = 0;
    int fp = 1, sp = 2;
    int used = 1;
    if (state[1] == 0 || state[2] == 0) {
        used = 0;
        fp = 0;
        if (state[1] == 0) sp = 1;
        else sp = 2;
    }
    for (int i = 2; i < 142; i++) {
        re = use_machine({fp, 2*i - 1, sp, 2*i});
        if (re == 0) {
            state[2*i-1] = used;
            state[2*i] = used;
        }
        else if (re == 1) {
            state[2*i-1] = used;
            if (used) state[2*i] = 0;
            else state[2*i] = 1;
        }
        else if (re == 2) {
            state[2*i] = used;
            if (used) state[2*i-1] = 0;
            else state[2*i-1] = 1;
        }
        else {
            if (used) {
                state[2*i-1] = 0;
                state[2*i] = 0;
            }
            else {
                state[2*i-1] = 1;
                state[2*i] = 1;
            }
        }
    }
    int counta = 0;
    for (int i = 0; i < 283; i++) {
        if (!state[i]) counta++;
    }
    int ans = counta;
    if (counta >= 142) {
        vector<int> m(2*counta);
        int pos = 1;
        for (int i = 0; i < 283; i++) {
            if (!state[i]) {
                m[pos] = i;
                pos += 2;
            }
        }
        int lastcal = 283;
        while (lastcal < n - counta) {
            for (int i = 0; i < counta; i++) {
                m[i*2] = lastcal + i + 1;
            }
            re = use_machine(m);
            re++;
            re /= 2;
            re = counta - re;
            ans += re;
            lastcal += counta;
        }
        vector<int> f;
        for (int i = 0; i < 2*(n - lastcal - 1); i++) {
            f.push_back(m[i]);
        }
        re = use_machine(f);
        re++;
        re /= 2;
        re = counta - re;
        ans += re;
        return ans;
    }
    else {
        int countb = 283 - counta;
        vector<int> m(2*countb);
        int pos = 1;
        for (int i = 0; i < 283; i++) {
            if (state[i]) {
                m[pos] = i;
                pos += 2;
            }
        }
        int lastcal = 283;
        while (lastcal < n - countb) {
            for (int i = 0; i < countb; i++) {
                m[i*2] = lastcal + i + 1;
            }
            re = use_machine(m);
            re++;
            re /= 2;
            ans += re;
            lastcal += countb;
        }
        vector<int> f;
        for (int i = 0; i < 2*(n - lastcal - 1); i++) {
            f.push_back(m[i]);
        }
        re = use_machine(f);
        re++;
        re /= 2;
        ans += re;
        return ans;
    }
	// for (int i = 0; i < n; i++)
	// 	m.push_back(i);
	// int c1 = use_machine(m);
	// m = {0, 1};
	// int c2 = use_machine(m);
	// return c1+c2;
}

• Subtask 1: 0 / 100