Submission #563854

#TimeUsernameProblemLanguageResultExecution timeMemory
563854topovikCounting Mushrooms (IOI20_mushrooms)C++14
56.78 / 100
11 ms308 KiB
#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; i++) { vector <int> c = {0, i}; int g = use_machine(c); if (g == 0) a.pb(i); else b.pb(i); } 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:113:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for (int j = 0; j < a.size() && i < n; j++, i++)
      |                             ~~^~~~~~~~~~
mushrooms.cpp:128:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             for (int j = 0; j < b.size() && i < n; j++, i++)
      |                             ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...