Submission #494962

#	Time	Username	Problem	Language	Result	Execution time	Memory
494962		PiejanVDC	Counting Mushrooms (IOI20_mushrooms)	C++17	10 / 100	250 ms	736 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
#include "mushrooms.h"

int use_machine(vector<int> x);

int count_mushrooms(int n) {
    int a=1,b=0;
    int goal = (n+1)/2;
    int i=1;
    if(n == 1) return 1;
    if(n == 2) return (use_machine({0,1}) == 1 ? 1 : 2);
    vector<int>posA = {0},posB;
    while(a < goal && b < goal) {
        int x = use_machine({0,i});
        if(x) b++,posB.push_back(i);
        else a++,posA.push_back(i);
        i++;
    }
    bool use = (a == goal ? 1 : 0);
    int ans = a;
    while(i < n) {
        vector<int>check;
        int p = 0;
        int sz = n - i;
        int start = i;
        for(int k = 0 ; k < min(goal + goal - 1, 2*sz+1) ; k++) {
            if(k&1) check.push_back(i++);
            else check.push_back((use ? posA[p++] : posB[p++]));
        }
        int nd = i-1;
        int cnt = use_machine(check);
        /*cout << "Checked range [" << start << " , " << nd << "]\n";
        cout << "Result: " << cnt << "\n";
        cout << "Added to answer: " << min(goal - 1,sz) - cnt/2 << "\n";
        cout << "-----------\n";*/
        if(use)
            ans += min(goal - 1,sz) - cnt/2;
        else
            ans += cnt/2;
        assert(goal - 1 - cnt/2 >= 0);
    }
    return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:26:13: warning: unused variable 'start' [-Wunused-variable]
   26 |         int start = i;
      |             ^~~~~
mushrooms.cpp:31:13: warning: unused variable 'nd' [-Wunused-variable]
   31 |         int nd = i-1;
      |             ^~

• Subtask 1: 10 / 100