제출 #825508

#제출 시각아이디문제언어결과실행 시간메모리
825508benjaminkleyn버섯 세기 (IOI20_mushrooms)C++17
36.87 / 100
11 ms436 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; set<int> A, B; bool recurse(int l, int r, bool a = true) { vector<int> query(r - l + 1); iota(query.begin(), query.end(), l); int x = use_machine(query); if (x == query.size() - 1) { if (a) { for (int i = l; i <= r; i += 2) A.insert(i); for (int i = l + 1; i <= r; i += 2) B.insert(i); return x % 2 == 0; } else { for (int i = l; i <= r; i += 2) B.insert(i); for (int i = l + 1; i <= r; i += 2) A.insert(i); return x % 2 == 1; } } if (x == 0) { if (a) { for (int i = l; i <= r; i++) A.insert(i); return true; } else { for (int i = l; i <= r; i++) B.insert(i); return false; } } int m = (l + r) / 2; return recurse(m, r, recurse(l, m, a)); } int count_mushrooms(int n) { A.insert(0); int i = 1; if (n >= 320) { recurse(0, 319); i = 320; } int cnt = A.size(); while (i < n) { vector<int> query; if (A.size() >= B.size()) { for (int j : A) { query.push_back(j); query.push_back(i++); if (i >= n) break; } int x = use_machine(query); cnt += query.size() / 2 - (x + 1) / 2; if (x % 2) B.insert(query.back()); else A.insert(query.back()); } else { for (int j : B) { query.push_back(j); query.push_back(i++); if (i >= n) break; } int x = use_machine(query); cnt += (x + 1) / 2; if (x % 2) A.insert(query.back()); else B.insert(query.back()); } } return cnt; }

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

mushrooms.cpp: In function 'bool recurse(int, int, bool)':
mushrooms.cpp:12:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if (x == query.size() - 1)
      |         ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...