Submission #303807

#	Time	Username	Problem	Language	Result	Execution time	Memory
303807		temurbek_khujaev	Counting Mushrooms (IOI20_mushrooms)	C++17	92.24 / 100	17 ms	436 KiB

mushrooms

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

using namespace std;

int count_mushrooms(int n) {
        vector<int> a = {0};
        vector<int> b;
        int pos = 1;
        if (n > 2000) {
            while (a.size() < 2 && b.size() < 2) {
                int res = use_machine({0, pos});
                if (res == 0) a.push_back(pos);
                else b.push_back(pos);
                pos++;
            }

            int k = 145;
            int p = 20000 / k - k / 2;
            for (int i = 0; i < p; i++) {
                if (a.size() >= 2) {
                    int res = use_machine({a[0], pos, a[1], pos + 1});
                    if (res & 2) b.push_back(pos); else a.push_back(pos);
                    if (res & 1) b.push_back(pos + 1); else a.push_back(pos + 1);
                } else {
                    int res = use_machine({b[0], pos, b[1], pos + 1});
                    if (res & 2) a.push_back(pos); else b.push_back(pos);
                    if (res & 1) a.push_back(pos + 1); else b.push_back(pos + 1);
                }
                pos += 2;
            }
        }
        int cnta = a.size();
        while (pos < n) {
            vector<int> q;
            if (a.size() > b.size()) {
                int f = min(n - pos, (int) a.size());
                for (int i = 0; i < f; i++) {
                    q.push_back(a[i]);
                    q.push_back(pos++);
                }
                int res = use_machine(q);
                if (res & 1) {
                    b.push_back(q.back());
                } else a.push_back(q.back());
                cnta += f - (res + 1) / 2;
            } else {
                int f = min(n - pos, (int) b.size());
                for (int i = 0; i < f; i++) {
                    q.push_back(b[i]);
                    q.push_back(pos++);
                }
                int res = use_machine(q);
                if (res & 1) {
                    a.push_back(q.back());
                } else b.push_back(q.back());
                cnta += (res + 1) / 2;
            }
        }
        return cnta;

}

• Subtask 1: 92.2449 / 100