oj.uz

Submission #1037258

# Submission time Handle Problem Language Result Execution time Memory
1037258 2024-07-28T11:43:30 Z Zicrus Counting Mushrooms (IOI20_mushrooms) C++17
0 / 100
 0 ms 344 KB 
#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 (used[G[id]]) return 0;
            if (used[kMost[i]]) return 0;
            tst.push_back(G[id++]);
            tst.push_back(kMost[i]);
            used[G[id]] = used[kMost[i]] = true;
            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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Answer is not correct.
4 Halted 0 ms 0 KB -