Submission #584271

#	Time	Username	Problem	Language	Result	Execution time	Memory
584271		LucaIlie	Counting Mushrooms (IOI20_mushrooms)	C++17	53.30 / 100	12 ms	388 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

int count_mushrooms( int n ) {
    int k, bs, nrA, p;
    vector <int> a, s( n );

    k = min( n, max( 3, (int)sqrt( n ) ) );
    s[0] = 0;
    nrA = 1;
    for ( int i = 1; i < k; i++ ) {
        s[i] = use_machine( { 0, i } );
        nrA += (s[i] == 0);
    }

    if ( nrA > k / 2 ) {
        bs = nrA - 1;
        p = 0;
    } else {
        bs = k - nrA - 1;
        p = 1;
    }
    for ( int i = 0; i < k; i++ ) {
        if ( s[i] == p )
            a.push_back( i );
    }

    for ( int i = k; i < n; i += bs ) {
        int j;
        vector <int> m;

        for ( j = 0; j < a.size() - 1 && i + j < n; j++ ) {
            m.push_back( a[j] );
            m.push_back( i + j );
        }
        m.push_back( a.back() );

        if ( p == 0 )
            nrA += j - use_machine( m ) / 2;
        else
            nrA += use_machine( m ) / 2;
    }

    return nrA;
}

Compilation message (stderr)

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

• Subtask 1: 53.3019 / 100