#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "mushrooms.h"
using namespace std;
template<typename X,typename Y> bool ckmin(X& x,Y y){return (x>y?x=y,1:0);}
using ii = pair<int,int>;
int use_machine(vector<int> x);
int count_mushrooms(int n){
vector<int>m;
vector<vector<int>>v(2,vector<int>());
int k = (n<=500?100:75), x, y, type = 0;
if(n<=226){
int ans = 1;
for(int i=1;i<n;++i)ans += (1 - use_machine({0,i}));
return ans;
}
v[0].pb(0);
int r1 = use_machine({0,1}), r2 = use_machine({0,2});
if(r1)v[1].pb(1);
else v[0].pb(1);
if(r2)v[1].pb(2);
else v[0].pb(2);
if(!r1)x = 0, y = 1;
else if(!r2)x = 0, y = 2;
else x = 1, y = 2, type = 1;
for(int i=3;i<2*k-1;i+=2){
assert(i+1<n);
int cur = use_machine({i,x,i+1,y});
if(cur&1)v[type^1].pb(i);
else v[type].pb(i);
if(cur>=2)v[type^1].pb(i+1);
else v[type].pb(i+1);
}
//deve dar uns 80 pontos
int target = (sz(v[0])>=k?0:1), ans = sz(v[0]);
for(int i=2*k-1;i<n;i+=k){
if(sz(v[target^1])>sz(v[target]))target ^= 1;
k = sz(v[target]);
vector<int>ask;
for(int j=0;j<k&&i+j<n;++j){
ask.pb(i+j), ask.pb(v[target][j]);
}
int cur = use_machine(ask);
if(cur&1)v[target^1].pb(i);
else v[target].pb(i);
if(target==1)ans += (cur+1)/2;
else ans += min(n-i,k) - (cur+1)/2;
}
return ans;
}
// 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;
// }
Compilation message
mushrooms.cpp:82:1: warning: multi-line comment [-Wcomment]
82 | // #define FMT_TO_STR(fmt, result) va_list vargs; va_start(vargs, fmt); \
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
208 KB |
Output is correct |
| 6 |
Correct |
2 ms |
208 KB |
Output is correct |
| 7 |
Correct |
6 ms |
208 KB |
Output is correct |
| 8 |
Correct |
7 ms |
208 KB |
Output is correct |
| 9 |
Correct |
6 ms |
208 KB |
Output is correct |
| 10 |
Correct |
8 ms |
208 KB |
Output is correct |
| 11 |
Partially correct |
7 ms |
320 KB |
Output is partially correct |
| 12 |
Correct |
7 ms |
208 KB |
Output is correct |
| 13 |
Correct |
7 ms |
208 KB |
Output is correct |
| 14 |
Correct |
4 ms |
312 KB |
Output is correct |
| 15 |
Partially correct |
8 ms |
304 KB |
Output is partially correct |
| 16 |
Partially correct |
6 ms |
308 KB |
Output is partially correct |
| 17 |
Correct |
4 ms |
308 KB |
Output is correct |
| 18 |
Correct |
6 ms |
208 KB |
Output is correct |
| 19 |
Partially correct |
5 ms |
332 KB |
Output is partially correct |
| 20 |
Correct |
6 ms |
208 KB |
Output is correct |
| 21 |
Correct |
6 ms |
312 KB |
Output is correct |
| 22 |
Partially correct |
6 ms |
208 KB |
Output is partially correct |
| 23 |
Correct |
6 ms |
208 KB |
Output is correct |
| 24 |
Correct |
4 ms |
336 KB |
Output is correct |
| 25 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 26 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 27 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 28 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 29 |
Partially correct |
6 ms |
320 KB |
Output is partially correct |
| 30 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 31 |
Partially correct |
7 ms |
312 KB |
Output is partially correct |
| 32 |
Partially correct |
7 ms |
312 KB |
Output is partially correct |
| 33 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 34 |
Partially correct |
6 ms |
208 KB |
Output is partially correct |
| 35 |
Partially correct |
8 ms |
336 KB |
Output is partially correct |
| 36 |
Partially correct |
6 ms |
208 KB |
Output is partially correct |
| 37 |
Partially correct |
5 ms |
208 KB |
Output is partially correct |
| 38 |
Partially correct |
6 ms |
208 KB |
Output is partially correct |
| 39 |
Partially correct |
6 ms |
328 KB |
Output is partially correct |
| 40 |
Partially correct |
7 ms |
208 KB |
Output is partially correct |
| 41 |
Partially correct |
6 ms |
324 KB |
Output is partially correct |
| 42 |
Partially correct |
6 ms |
328 KB |
Output is partially correct |
| 43 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 44 |
Partially correct |
8 ms |
336 KB |
Output is partially correct |
| 45 |
Partially correct |
5 ms |
208 KB |
Output is partially correct |
| 46 |
Partially correct |
6 ms |
316 KB |
Output is partially correct |
| 47 |
Partially correct |
6 ms |
320 KB |
Output is partially correct |
| 48 |
Partially correct |
6 ms |
340 KB |
Output is partially correct |
| 49 |
Partially correct |
8 ms |
336 KB |
Output is partially correct |
| 50 |
Partially correct |
6 ms |
340 KB |
Output is partially correct |
| 51 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 52 |
Partially correct |
5 ms |
312 KB |
Output is partially correct |
| 53 |
Partially correct |
7 ms |
332 KB |
Output is partially correct |
| 54 |
Partially correct |
6 ms |
436 KB |
Output is partially correct |
| 55 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 56 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 57 |
Partially correct |
6 ms |
208 KB |
Output is partially correct |
| 58 |
Partially correct |
7 ms |
332 KB |
Output is partially correct |
| 59 |
Partially correct |
5 ms |
336 KB |
Output is partially correct |
| 60 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 61 |
Partially correct |
7 ms |
320 KB |
Output is partially correct |
| 62 |
Correct |
0 ms |
208 KB |
Output is correct |
| 63 |
Correct |
0 ms |
208 KB |
Output is correct |
| 64 |
Correct |
0 ms |
208 KB |
Output is correct |
| 65 |
Correct |
0 ms |
208 KB |
Output is correct |
| 66 |
Correct |
0 ms |
208 KB |
Output is correct |
| 67 |
Correct |
0 ms |
208 KB |
Output is correct |
| 68 |
Correct |
0 ms |
208 KB |
Output is correct |
| 69 |
Correct |
1 ms |
208 KB |
Output is correct |
| 70 |
Correct |
0 ms |
208 KB |
Output is correct |
| 71 |
Correct |
1 ms |
208 KB |
Output is correct |
| 72 |
Correct |
0 ms |
208 KB |
Output is correct |
| 73 |
Correct |
1 ms |
208 KB |
Output is correct |
| 74 |
Correct |
1 ms |
208 KB |
Output is correct |
| 75 |
Correct |
0 ms |
208 KB |
Output is correct |
| 76 |
Correct |
0 ms |
208 KB |
Output is correct |
| 77 |
Correct |
0 ms |
208 KB |
Output is correct |
| 78 |
Correct |
1 ms |
208 KB |
Output is correct |
| 79 |
Correct |
0 ms |
208 KB |
Output is correct |
| 80 |
Correct |
0 ms |
208 KB |
Output is correct |
| 81 |
Correct |
1 ms |
208 KB |
Output is correct |
| 82 |
Correct |
0 ms |
208 KB |
Output is correct |
| 83 |
Correct |
0 ms |
208 KB |
Output is correct |
| 84 |
Correct |
0 ms |
208 KB |
Output is correct |
| 85 |
Correct |
1 ms |
208 KB |
Output is correct |
| 86 |
Correct |
0 ms |
208 KB |
Output is correct |
| 87 |
Correct |
1 ms |
208 KB |
Output is correct |
| 88 |
Correct |
0 ms |
208 KB |
Output is correct |
| 89 |
Correct |
0 ms |
208 KB |
Output is correct |
| 90 |
Correct |
0 ms |
208 KB |
Output is correct |
| 91 |
Correct |
0 ms |
208 KB |
Output is correct |
