Submission #522978

#	Time	Username	Problem	Language	Result	Execution time	Memory
522978		dxz05	Counting Mushrooms (IOI20_mushrooms)	C++14	80.71 / 100	12 ms	452 KiB

mushrooms

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

using namespace std;

int f(int k){
    return 2 + k + (20000 - 2 * k - 3 + k) / (k + 1);
}

int get_k(){
    int k = 1;
    for (int i = 1; i <= 20000; i++){
        if (f(i) < f(k)) k = i;
    }
    return k;
}

int count_mushrooms(int n) {
    if (n <= 227){
        int res = 1;
        for (int i = 1; i < n; i++){
            res += use_machine({0, i}) == 0;
        }
        return res;
    }
    vector<int> A = {0}, B;

    int k = 136;

    int i = 1;
    while (i < 3){
        if (use_machine({0, i}) == 0) A.push_back(i); else
            B.push_back(i);
        i++;
    }

    int res = A.size();

    while (i < n){
        vector<int> r;
        if (A.size() > B.size()){
            for (int x : A){
                if (i >= n) break;
                r.push_back(x);
                r.push_back(i);
                i++;
            }

            int cnt = use_machine(r);
            if (cnt & 1) B.push_back(r.back()); else
                A.push_back(r.back());
            res += r.size() / 2 - (cnt + 1) / 2;
        } else {
            for (int x : B){
                if (i >= n) break;
                r.push_back(x);
                r.push_back(i);
                i++;
            }
            int cnt = use_machine(r);
            if (cnt & 1) A.push_back(r.back()); else
                B.push_back(r.back());
            res += (cnt + 1) / 2;
        }
    }

    return res;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:28:9: warning: unused variable 'k' [-Wunused-variable]
   28 |     int k = 136;
      |         ^

• Subtask 1: 80.7143 / 100