Submission #1037242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037242		Zicrus	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	6 ms	1216 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
 
typedef long long ll;
 
int count_mushrooms(int n) {
    vector<ll> kCnt = {1, 0};
    vector<vector<ll>> known(2);
    known[0].push_back(0);
    ll t = use_machine({0, 1});
    known[t].push_back(1);
    kCnt[t]++;
    if (t == 1) {
        t = use_machine({0, 2});
        known[t].push_back(2);
        kCnt[t]++;
    }
    while (kCnt[0] + kCnt[1] < n) {
        ll sumK = kCnt[0] + kCnt[1];
        ll kVal = known[0].size() > known[1].size() ? 0 : 1;
        vector<ll> &kMost = kVal ? known[1] : known[0];
        vector<int> tst;
        ll id = sumK;
        ll nw2Cnt = -1;
        for (int i = 0; i < kMost.size() && id < n; i++) {
            tst.push_back(id++);
            tst.push_back(kMost[i]);
            nw2Cnt++;
        }
        t = use_machine(tst);
        ll nwK = (t & 1) ^ kVal;
        known[nwK].push_back(sumK);
        kCnt[nwK]++;
        kCnt[1-kVal] += t/2;
        kCnt[kVal] += nw2Cnt - t/2;
    }
    return kCnt[0];
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int i = 0; i < kMost.size() && id < n; i++) {
      |                         ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 100