Submission #1018838

#TimeUsernameProblemLanguageResultExecution timeMemory
1018838BoasCounting Mushrooms (IOI20_mushrooms)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; int use_machine(std::vector<int> x); #define loop(x, i) for (int i = 0; i < x; i++) #define pb push_back #define ALL(x) (x).begin(), (x).end() typedef vector<int> vi; typedef pair<int, int> ii; typedef set<int> si; typedef vector<vi> vvi; int count_mushrooms(int n) { vi A = {0}, B; int c1 = use_machine({0, 1}); int i = 2; if (c1 == 1) { if (n == 2) return 1; B.pb(1); int c2 = use_machine({1, 2}); i++; if (c2 == 1) A.pb(2); else B.pb(2); } else { A.pb(1); } int x = sqrt(n); assert(x>=1); while (max(A.size(), B.size()) < x) { if (A.size() >= 2) { if (i + 1 >= n) break; int res = use_machine({A[0], i, A[1], i + 1}); if (res == 0) { A.pb(i); A.pb(i + 1); } else if (res == 1) { A.pb(i); } else if (res == 2) { A.pb(i + 1); } i += 2; } else { if (i + 1 >= n) break; int res = use_machine({B[0], i, B[1], i + 1}); if (res == 3) { A.pb(i); A.pb(i + 1); } else if (res == 2) { A.pb(i); } else if (res == 1) { A.pb(i + 1); } i += 2; } } if (i == n - 1) { if (use_machine({0, i}) == 0) A.pb(i); i++; } int res = A.size(); for (; i < n; i += x) { vi q; if (A.size() >= x) { int l = min(x, n - i); loop(l, j) { q.pb(A.at(j)); q.pb(i + j); } int c3 = use_machine(q); if (c3 % 2 == 1) c3++; res += l - (c3 / 2); q.clear(); } else { int l = min(x, n - i); loop(l, j) { q.pb(B.at(j)); q.pb(i + j); } int c3 = use_machine(q); if (c3 % 2 == 1) c3++; res += (c3 / 2); q.clear(); } } return res; } 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; 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", answer); fclose(stdout); fclose(stdin); return 0; }

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:38:33: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'int' [-Wsign-compare]
   38 |  while (max(A.size(), B.size()) < x)
      |         ~~~~~~~~~~~~~~~~~~~~~~~~^~~
mushrooms.cpp:91:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |         if (A.size() >= x)
      |             ~~~~~~~~~^~~~
/usr/bin/ld: /tmp/ccogE9mG.o: in function `use_machine(std::vector<int, std::allocator<int> >)':
stub.cpp:(.text+0x150): multiple definition of `use_machine(std::vector<int, std::allocator<int> >)'; /tmp/ccGC1u9I.o:mushrooms.cpp:(.text+0x220): first defined here
/usr/bin/ld: /tmp/ccogE9mG.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccGC1u9I.o:mushrooms.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status