Submission #531136

#	Time	Username	Problem	Language	Result	Execution time	Memory
531136		ColourAttila	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	0 ms	200 KiB

mushrooms

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

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;
vector<int> knownA , knownB, ask;

int cnt;

int query1(vector<int> a) {
    int res = use_machine(a);

    if(res == 1)  {
        knownB.push_back(a.back());
    }
    else {
        knownA.push_back(a.back());
    }

    return res;
}

int query2(vector<int> a, bool type) {
    int res = use_machine(a);
    //cout << "type: " << type << endl;

    if(((res & 2) == 2) == type) {
        knownB.push_back(a[1]);
    }
    else {
        knownA.push_back(a[1]);
    }

    if(((res & 1) == 1) == type) {
        knownB.push_back(a.back());
    }
    else {
        knownA.push_back(a.back());
    }

    return res;
}

int query3(vector<int> a, bool type) {
    int res = use_machine(a);


    if(type) {
        cnt += (a.size() - res) / 2;
        if(!(res % 2)) knownA.push_back(a.back());
        else knownB.push_back(a.back());
    }
    else {
        cnt += (res + 1) / 2;
        if(res % 2) knownA.push_back(a.back());
        else knownB.push_back(a.back());
    }

    return res;
}

int count_mushrooms(int n){
    knownA.push_back(0);
    ask = {0, 1};

    int curr = 1;

    // van legalabb 2
    int res = query1(ask);
    if(res == 1) {
        ask[1] = 2;
        query1(ask);
        curr++;
    }

    int sq = sqrt(n);

    //gyöknyi ugyanolyan keresese
    while(knownA.size() < sq && knownB.size() < sq) {
        ask.clear();
        
        bool type;
        if(knownA.size() > 1) {
            ask = {knownA[0], ++curr, knownA[1], ++curr};
            type = 1;
        }
        else {
            ask = {knownB[0], ++curr, knownB[1], ++curr};
            type = 0;
        }

        query2(ask, type);
    }

    // megoldas
    cnt = knownA.size();
    while(curr < n) {
        ask.clear();
        bool type;
        
        if(knownA.size() > knownB.size()) {
            type = 1;
            for(int i = 0; i < knownA.size(); i++) {
                ask.push_back(knownA[i]);
                ask.push_back(++curr);
                if(curr == n) break;
            }
        }
        else {
            type = 2;
            for(int i = 0; i < knownB.size(); i++) {
                ask.push_back(knownB[i]);
                ask.push_back(++curr);
                if(curr == n) break;
            }
        }

        query3(ask, type);
    }

    return cnt;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:81:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |     while(knownA.size() < sq && knownB.size() < sq) {
      |           ~~~~~~~~~~~~~~^~~~
mushrooms.cpp:81:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |     while(knownA.size() < sq && knownB.size() < sq) {
      |                                 ~~~~~~~~~~~~~~^~~~
mushrooms.cpp:105:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for(int i = 0; i < knownA.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~~
mushrooms.cpp:113:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for(int i = 0; i < knownB.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 100