Submission #1246924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246924		qwusha	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	1 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 use_machine(vector<int> q) {
    for (auto el : q) {
        cout << el << ' ';
    }
    cout << endl;
    int x;
    cin >> x;
    return x;
}
*/

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,3); 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 (ca > cb) {
        for (int i = num; i < min(n - 1,280); i+=2) {
            vector<int> q = {a[0], i, a[1], i + 1};
            int x = use_machine(q);
            if (x == 0) {
                ca+= 2;
                a.push_back(i);
                a.push_back(i + 1);
            } else if (x == 1) {
                cb++;
                ca++;
                b.push_back(i + 1);
                a.push_back(i);
            } else if (x == 2) {
                cb++;
                ca++;
                a.push_back(i + 1);
                b.push_back(i);
            } else {
                cb+=2;
                b.push_back(i + 1);
                b.push_back(i);
            }
            num+=2;
        }
    } else {
        for (int i = num; i < min(n - 1,265); i+=2) {
            vector<int> q = {b[0], i, b[1], i + 1};
            int x = use_machine(q);
            if (x == 3) {
                ca+= 2;
                a.push_back(i);
                a.push_back(i + 1);
            } else if (x == 2) {
                cb++;
                ca++;
                b.push_back(i + 1);
                a.push_back(i);
            } else if (x == 1) {
                cb++;
                ca++;
                a.push_back(i + 1);
                b.push_back(i);
            } else {
                cb+=2;
                b.push_back(i + 1);
                b.push_back(i);
            }
            num+=2;
        }
    }
    if (num == n) {
        return ca;
    }
    int res = ca;
    for (int i = num; i < n; i += (ca)) {
        if (ca > cb) {
            vector<int> q(ca * 2);
            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);
            if (x % 2 == 1) {
                b.push_back(q.back());
                cb++;
            } else {
                a.push_back(q.back());
                ca++;
            }
            res += (pos) - (x + 1) / 2;
        } else {
            vector<int> q(cb * 2);
            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);
            if (x % 2 == 0) {
                b.push_back(q.back());
                cb++;
            } else {
                a.push_back(q.back());
                ca++;
            }
            res += (x + 1) / 2;

        }
    }
    return res;


}


/*
signed main() {
    int n;
    cin >> n;
    int res = count_mushrooms(n);
    cout << res << '\n';
}
*/

• Subtask 1: 0 / 100