Submission #1037259

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

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
 
typedef long long ll;
 
int count_mushrooms(int n) {
    vector<int> G(n);
    for (int i = 0; i < n; i++) G[i] = i;
    mt19937 mt(time(0));
    //shuffle(G.begin()+1, G.end(), mt);

    vector<ll> kCnt = {1, 0};
    vector<vector<ll>> known(2);
    known[0].push_back(G[0]);
    ll t = use_machine({G[0], G[1]});
    known[t].push_back(G[1]);
    kCnt[t]++;
    if (t == 1) {
        t = use_machine({G[0], G[2]});
        known[t].push_back(G[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;
        vector<bool> used(n);
        for (int i = 0; i < kMost.size() && id < n; i++) {
            if (G[kMost[i]] >= G[sumK]) return 0;
            tst.push_back(G[id++]);
            tst.push_back(kMost[i]);
            nw2Cnt++;
        }
        t = use_machine(tst);
        ll nwK = (t & 1) ^ kVal;
        known[nwK].push_back(G[sumK]);
        kCnt[nwK]++;
        kCnt[1-kVal] += t/2;
        kCnt[kVal] += nw2Cnt - t/2;
        if (nw2Cnt == 1) {
            known[(t/2) ^ kVal].push_back(G[sumK+1]);
        }
    }
    return kCnt[0];
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100