Submission #563866

#	Time	Username	Problem	Language	Result	Execution time	Memory
563866		topovik	Counting Mushrooms (IOI20_mushrooms)	C++14	77.93 / 100	15 ms	316 KiB

mushrooms

#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <string>
#define f first
#define s second
#define pb push_back
#include "mushrooms.h"

using namespace std;

//static char fmt_buffer[100000];
//#define FMT_TO_STR(fmt, result) va_list vargs; va_start(vargs, fmt); \
//	vsnprintf(fmt_buffer, sizeof(fmt_buffer), fmt, vargs); \
//	va_end(vargs); fmt_buffer[sizeof(fmt_buffer)-1] = 0; \
//	std::string result(fmt_buffer);
//
//static const int min_n = 2;
//static const int max_n = 20000;
//static const int max_qc = 20000;
//static const int max_qs = 100000;
//static const int species_A = 0;
//static const int species_B = 1;
//
//static int n;
//static std::vector<int> species;
//static int qc, qs;
//
//int count_mushrooms(int);
//
//static inline void error_if(bool cond, std::string message) {
//	if (cond) {
//		printf("%s\n", message.c_str());
//		exit(0);
//	}
//}
//
//static inline void wrong_if(bool cond, std::string message) {
//	error_if(cond, "Wrong Answer: "+message);
//}
//
//int use_machine(std::vector<int> x) {
//	const int xs = x.size();
//	wrong_if(xs < 2, "Too small array for query.");
//	wrong_if(xs > n, "Too large array for query.");
//	qc++;
//	wrong_if(qc > max_qc, "Too many queries.");
//	qs += xs;
//	wrong_if(qs > max_qs, "Too many total array sizes as queries.");
//	for (int i = 0; i < xs; i++)
//		wrong_if(x[i] < 0 || n - 1 < x[i], "Invalid value in the query array.");
//	std::vector<bool> used(n, false);
//	for (int i = 0; i < xs; i++) {
//		wrong_if(used[x[i]], "Duplicate value in the query array.");
//		used[x[i]] = true;
//	}
//	int diffs = 0;
//	for (int i = 1; i < xs; i++)
//		diffs += int(species[x[i]] != species[x[i-1]]);
//	return diffs;
//}
//
//#ifdef __GNUC__
//__attribute__ ((format(printf, 2, 3)))
//#endif
//static inline void check_input(bool cond, const char* message_fmt, ...) {
//	FMT_TO_STR(message_fmt, message);
//	error_if(!cond, "Invalid input: "+message);
//}
//
//int main() {
//	check_input(1 == scanf("%d", &n), "Could not read n.");
//	check_input(min_n <= n, "n must not be less than %d, but it is %d.", min_n, n);
//	check_input(n <= max_n, "n must not be greater than %d, but it is %d.", max_n, n);
//	species.resize(n);
//	for (int i = 0; i < n; i++) {
//		check_input(1 == scanf("%d", &species[i]), "Could not read species element [%d].", i);
//		check_input(species[i]==species_A || species[i] == species_B,
//					"Species elements must be %d or %d, but species element [%d] is %d.", species_A, species_B, i, species[i]);
//	}
//	check_input(species[0] == species_A, "Species element [%d] must be %d.", 0, species_A);
//	// Postponed closing standard input in order to allow interactive usage of the grader.
//
//	qc = 0;
//	qs = 0;
//	int answer = count_mushrooms(n);
//	printf("%d\n%d\n", answer, qc);
//	fclose(stdout);
//	fclose(stdin);
//	return 0;
//}

const int M = 110;

int count_mushrooms(int n) {
    vector <int> a, b;
    a.pb(0);
    int i = 0;
    for (i = 1; a.size() < M && b.size() < M && i < n; )
    {
        if ((a.size() < 2 && b.size() < 2) || (i == n - 1))
        {
            vector <int> c = {0, i};
            int g = use_machine(c);
            if (g == 0) a.pb(i);
            else b.pb(i);
            i++;
            continue;
        }
        if (a.size() >= 2)
        {
            vector <int> c = {a[0], i, a[1], i + 1};
            int x = use_machine(c);
            if (x == 0)
            {
                a.pb(i);
                a.pb(i + 1);
            }
            if (x == 1)
            {
                b.pb(i + 1);
                a.pb(i);
            }
            if (x == 2)
            {
                b.pb(i);
                a.pb(i + 1);
            }
            if (x == 3)
            {
                b.pb(i);
                b.pb(i + 1);
            }
            i += 2;
            continue;
        }
        if (b.size() >= 2)
        {
            vector <int> c = {b[0], i, b[1], i + 1};
            int x = use_machine(c);
            if (x == 0)
            {
                b.pb(i);
                b.pb(i + 1);
            }
            if (x == 1)
            {
                a.pb(i + 1);
                b.pb(i);
            }
            if (x == 2)
            {
                a.pb(i);
                b.pb(i + 1);
            }
            if (x == 3)
            {
                a.pb(i);
                a.pb(i + 1);
            }
            i += 2;
            continue;
        }
    }
    if (a.size() >= M)
    {
        int ans = a.size();
        for (; i < n; )
        {
            vector <int> c;
            for (int j = 0; j < a.size() && i < n; j++, i++)
            {
                c.pb(i);
                c.pb(a[j]);
            }
            ans += (c.size() / 2) - ((use_machine(c) + 1) / 2);
        }
        return ans;
    }
    if (b.size() >= M)
    {
        int ans = a.size();
        for (; i < n; )
        {
            vector <int> c;
            for (int j = 0; j < b.size() && i < n; j++, i++)
            {
                c.pb(i);
                c.pb(b[j]);
            }
            ans += ((use_machine(c) + 1) / 2);
        }
        return ans;
    }
    return a.size();
}

Compilation message (stderr)

mushrooms.cpp:14:1: warning: multi-line comment [-Wcomment]
   14 | //#define FMT_TO_STR(fmt, result) va_list vargs; va_start(vargs, fmt); \
      | ^
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:172:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |             for (int j = 0; j < a.size() && i < n; j++, i++)
      |                             ~~^~~~~~~~~~
mushrooms.cpp:187:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |             for (int j = 0; j < b.size() && i < n; j++, i++)
      |                             ~~^~~~~~~~~~

• Subtask 1: 77.931 / 100