Submission #1244586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244586		qwusha	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 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 - 1,229); i+= 2) {
        vector<int> q = {i + 1, 0, i};
        int x = use_machine(q);
        if (x == 0) {
            ca += 2;
            a.push_back(i);
            a.push_back(i + 1);
        } else if (x == 2) {
            cb += 2;
            b.push_back(i);
            b.push_back(i + 1);
        } else {
            ca++;
            cb++;
            q = {i, 0};
            x = use_machine(q);
            if (x == 0) {
                a.push_back(i);
                b.push_back(i + 1);
            } else {
                a.push_back(i + 1);
                b.push_back(i);
            }
        }
        num+= 2;
    }
    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: 0 / 100