제출 #421710

#제출 시각아이디문제언어결과실행 시간메모리
421710usachevd0버섯 세기 (IOI20_mushrooms)C++17
80.14 / 100
11 ms456 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "mushrooms.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& e : v) stream << e << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } int use_machine(vector<int> x); int count_mushrooms_halfn(int n) { if (n == 2) { if (use_machine({0, 1}) == 1) return 1; return 2; } int ans = 1; int x, y; int i; if (use_machine({0, 1}) == 0) { x = 0; y = 1; i = 2; ++ans; } else if (use_machine({0, 2}) == 0) { x = 0; y = 2; i = 3; ++ans; } else { x = 1; y = 2; i = 3; } for (; i < n; i += 2) { if (i == n - 1) { ans += use_machine({0, i}) == 0; break; } int res = use_machine({x, i, y, i + 1}); if (x == 0) { if (res == 0) ans += 2; else if (res <= 2) ++ans; } else { if (res == 3) ans += 2; else if (res >= 1) ++ans; } } return ans; } int CeilD(int x, int y) { if (x % y) return x / y + 1; return x / y; } int count_mushrooms(int n) { if (n <= 2) { return 1 + (int)(use_machine({0, 1}) == 0); } const int maxS = 1e5; int maxQ = n; int asked = 0; int askedSum = 0; auto ask = [&](vector<int> x) { // debug(x); ++asked; askedSum += x.size(); assert(asked <= maxQ); assert(askedSum <= maxS); return use_machine(x); }; int minVal = 1e9; int minK = -1; for (int k = 1; k <= n; ++k) { if (2 * k >= n) break; if (chkmin(minVal, k + CeilD(n, k))) { minK = k; } } int k = minK; // debug(k); vector<int> col(n, -1); col[0] = 0; vector<int> h[2]; h[0].push_back(0); for (int i = 1; i <= 2; ++i) { col[i] = ask({0, i}); h[col[i]].push_back(i); } int i = 3; if (h[0].size() >= 2) { while (true) { if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break; int res = ask({h[0][0], i, h[0][1], i + 1}); if (res == 0) { col[i] = col[i + 1] = 0; } else if (res == 1) { col[i] = 0; col[i + 1] = 1; } else if (res == 2) { col[i] = 1; col[i + 1] = 0; } else { col[i] = col[i + 1] = 1; } h[col[i]].push_back(i); h[col[i + 1]].push_back(i + 1); i += 2; } } else { while (true) { if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break; int res = ask({h[1][0], i, h[1][1], i + 1}); if (res == 3) { col[i] = col[i + 1] = 0; } else if (res == 2) { col[i] = 0; col[i + 1] = 1; } else if (res == 1) { col[i] = 1; col[i + 1] = 0; } else { col[i] = col[i + 1] = 1; } h[col[i]].push_back(i); h[col[i + 1]].push_back(i + 1); i += 2; } } int ans = h[0].size(); if (h[0].size() >= h[1].size()) { int k = h[0].size() - 1; for (; i < n; i += k) { int m = min(n, i + k) - i; vector<int> x = {h[0][0]}; for (int j = 0; j < m; ++j) { x.push_back(i + j); x.push_back(h[0][j + 1]); } ans += m - ask(x) / 2; } } else { int k = h[1].size() - 1; for (; i < n; i += k) { int m = min(n, i + k) - i; vector<int> x = {h[1][0]}; for (int j = 0; j < m; ++j) { x.push_back(i + j); x.push_back(h[1][j + 1]); } ans += ask(x) / 2; } } return ans; } #ifdef LOCAL 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() { freopen("in", "r", stdin); 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; } // int32_t main() { // #ifdef LOCAL // freopen("in", "r", stdin); // #endif // ios::sync_with_stdio(0); // cin.tie(0); // return 0; // } #endif

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

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:150:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |             if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
      |                 ~~~~~~~~~~~~^~~~~~~~
mushrooms.cpp:150:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |             if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
      |                                         ~~~~~~~~~~~~^~~~~~~~
mushrooms.cpp:170:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  170 |             if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
      |                 ~~~~~~~~~~~~^~~~~~~~
mushrooms.cpp:170:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  170 |             if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
      |                                         ~~~~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...