제출 #780987

#제출 시각아이디문제언어결과실행 시간메모리
780987Elias버섯 세기 (IOI20_mushrooms)C++17
0 / 100
1 ms276 KiB
#ifndef _DEBUG #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include <bits/stdc++.h> using namespace std; #ifdef _DEBUG int count_mushrooms(int n); int use_machine(std::vector<int> x); #endif #ifndef _DEBUG #include "mushrooms.h" #endif int count_mushrooms(int n) { int countA = 1; int countB = 0; set<int> a = {0}; set<int> b; int i = 1; while (a.size() < 2 && b.size() < 2) { if (use_machine({0, i})) { b.insert(i++); countB++; } else { a.insert(i++); countA++; } } bool swapped = false; if (b.size() > a.size()) { swap(a, b); swap(countA, countB); swapped ^= true; } while (a.size() * a.size() < (n - i) && b.size() * b.size() < (n - i)) { int output = use_machine({*a.begin(), i, *next(a.begin()), i + 1}); if (output & 2) a.insert(i); else b.insert(i); if (output & 1) a.insert(i + 1); else b.insert(i + 1); i += 2; } while (i != n) { if (b.size() > a.size()) { swap(a, b); swap(countA, countB); swapped ^= true; } vector<int> query; vector<int> copyA(a.begin(), a.end()); reverse(copyA.begin(), copyA.end()); while (i != n && copyA.size()) { query.push_back(copyA.back()); query.push_back(i++); } int output = use_machine(query); int newB = (output + 1) / 2; int newA = query.size() / 2 - newB; countA += newA; countB += newB; if (output & 1) { b.insert(query.back()); } else { a.insert(query.back()); } } if (swapped) { swap(a, b); swap(countA, countB); } return countA; } #ifdef _DEBUG 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%d\n", answer, qc); fclose(stdout); fclose(stdin); return 0; } #endif

컴파일 시 표준 에러 (stderr) 메시지

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:53:29: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |  while (a.size() * a.size() < (n - i) && b.size() * b.size() < (n - i))
      |         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
mushrooms.cpp:53:62: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |  while (a.size() * a.size() < (n - i) && b.size() * b.size() < (n - i))
      |                                          ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...