Submission #1244535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244535		qwusha	Counting Mushrooms (IOI20_mushrooms)	C++20	56.78 / 100	3 ms	428 KiB

mushrooms

#include "mushrooms.h"

#include <iostream>
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

int inf = 1e9 + 7;




int count_mushrooms(int n) {
    int ca = 1, cb = 0;
    vector<int> a = {0}, b;
    int num = 1;
    for (int i = 1; i < min(n,201); i++) {
        vector<int> q = {0, i};
        int x = use_machine(q);
        if (x == 0) {
            ca++;
            a.push_back(i);
        } else {
            cb++;
            b.push_back(i);
        }
        num++;
    }
    if (num == n) {
        return ca;
    }
    if (ca > cb) {
        int res = ca;
        for (int i = num; i < n; i += (ca - 1)) {
            vector<int> q(ca * 2 - 1);
            for (int j = 0; j < ca; j++) {
                q[j * 2] = a[j];
            }
            int ind = -1;
            int pos = 0;
            for (int j = 1; j < q.size(); j += 2) {
                q[j] = i + (j - 1) / 2;
                if (q[j] >= n) {
                    ind = j;
                    break;
                } else {
                    pos++;
                }
            }
            if (ind != -1) {
                int cur = q.size() - 1;
                while (cur >= ind) {
                    q.pop_back();
                    cur--;
                }
            }
            int x = use_machine(q);
            res += (pos) - x / 2;
        }
        return res;
    } else {
        int res = ca;
        for (int i = num; i < n; i += (cb - 1)) {
            vector<int> q(cb * 2 - 1);
            for (int j = 0; j < cb; j++) {
                q[j * 2] = b[j];
            }
            int ind = -1;
            for (int j = 1; j < q.size(); j += 2) {
                q[j] = i + (j - 1) / 2;
                if (q[j] >= n) {
                    ind = j;
                    break;
                }
            }
            if (ind != -1) {
                int cur = q.size() - 1;
                while (cur >= ind) {
                    q.pop_back();
                    cur--;
                }
            }
            int x = use_machine(q);
            res += x / 2;
        }
        return res;
    }

}

• Subtask 1: 56.7839 / 100