제출 #1246902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246902		qwusha	버섯 세기 (IOI20_mushrooms)	C++20	0 / 100	0 ms	420 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,3); i++) {
        vector<int> q = {0, i};
        int x = use_machine(q);
        if (x == 0) {
            ca++;
            a.push_back(i);
            if (a.size() == 2)
                break;
        } else {
            cb++;
            b.push_back(i);
        }
        num++;
    }
    if (ca > cb) {
        for (int i = num; i < min(n,300); 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,300); i+=2) {
            vector<int> q = {a[0], i, a[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;
    }
    if (ca > cb) {
        int res = ca;
        for (int i = num; i < n; i += (ca)) {
            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);
            res += (pos) - (x + 1) / 2;
        }
        return res;
    } else {
        int res = ca;
        for (int i = num; i < n; i += (cb)) {
            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);
            res += (x + 1) / 2;
        }
        return res;
    }

}

• Subtask 1: 0 / 100