Submission #413847

#	Time	Username	Problem	Language	Result	Execution time	Memory
413847		ivan24	Counting Mushrooms (IOI20_mushrooms)	C++14	75.84 / 100	12 ms	328 KiB

mushrooms

#include "mushrooms.h"

#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

class Solver{
private:
    ll n;
    vvi known;
    ll cnt[2];

    void typeZeroQuery (ll x){
        ll res = use_machine(vi{0,x});
        known[res].push_back(x);
    }

    void typeOneQuery(ll x1, ll x2){
        ll curType = 0;
        if (2 > known[0].size()) curType = 1;

        vi v = {known[curType][0],x1,known[curType][1],x2};

        ll res = use_machine(v);

        if (res & 2){
            known[1-curType].push_back(x1);
        }else{
            known[curType].push_back(x1);
        }

        if (res & 1){
            known[1-curType].push_back(x2);
        }else{
            known[curType].push_back(x2);
        }
    }

    ll typeTwoQuery (ll sptr){
        vi queryAr;
        ll curType = 0;

        ll ogsptr = sptr;

        if (known[curType].size() < known[1-curType].size()){
            curType = 1-curType;
        }

        for (ll i = 0; known[curType].size() > i && n > sptr; i++){
            queryAr.push_back(known[curType][i]);
            queryAr.push_back(sptr++);
        }

        ll res = use_machine(queryAr);
        res = (res+1)/2;

        cnt[1-curType] += res;
        cnt[curType] += (sptr-ogsptr) - res;

        return sptr;
    }

public:
    Solver(ll n): n(n){

    }

    ll solve(){

        cnt[0] = cnt[1] = 0;

        known.assign(2,vi());
        known[0].push_back(0);
        ll ptr = 1;

        for (; 3 > ptr && n > ptr;){
            typeZeroQuery(ptr++);
        }

        for (;2*n > ptr*ptr && n > ptr;){
            typeOneQuery(ptr,ptr+1);
            ptr += 2;
        }

        for (;n>ptr;){
            ptr = typeTwoQuery(ptr);
        }

        return known[0].size()+cnt[0];
    }
};

int count_mushrooms(int n) {
	Solver mySolver(n);
	return mySolver.solve();
}

Compilation message (stderr)

mushrooms.cpp: In member function 'll Solver::typeTwoQuery(ll)':
mushrooms.cpp:56:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   56 |         for (ll i = 0; known[curType].size() > i && n > sptr; i++){
      |                        ~~~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 75.8389 / 100