#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <string>
#define f first
#define s second
#define pb push_back
#include "mushrooms.h"
using namespace std;
//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;
//
//int count_mushrooms(int);
//
//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;
//}
const int M = 110;
int count_mushrooms(int n) {
vector <int> a, b;
a.pb(0);
int i = 0;
for (i = 1; a.size() < M && b.size() < M && i < n; )
{
if ((a.size() < 2 && b.size() < 2) || (i == n - 1))
{
vector <int> c = {0, i};
int g = use_machine(c);
if (g == 0) a.pb(i);
else b.pb(i);
i++;
continue;
}
if (a.size() >= 2)
{
vector <int> c = {a[0], i, a[1], i + 1};
int x = use_machine(c);
if (x == 0)
{
a.pb(i);
a.pb(i + 1);
}
if (x == 1)
{
b.pb(i + 1);
a.pb(i);
}
if (x == 2)
{
b.pb(i);
a.pb(i + 1);
}
if (x == 3)
{
b.pb(i);
b.pb(i + 1);
}
i += 2;
continue;
}
if (b.size() >= 2)
{
vector <int> c = {b[0], i, b[1], i + 1};
int x = use_machine(c);
if (x == 0)
{
b.pb(i);
b.pb(i + 1);
}
if (x == 1)
{
a.pb(i + 1);
b.pb(i);
}
if (x == 2)
{
a.pb(i);
b.pb(i + 1);
}
if (x == 3)
{
a.pb(i);
a.pb(i + 1);
}
i += 2;
continue;
}
}
if (a.size() >= M)
{
int ans = a.size();
for (; i < n; )
{
vector <int> c;
for (int j = 0; j < a.size() && i < n; j++, i++)
{
c.pb(i);
c.pb(a[j]);
}
ans += (c.size() / 2) - ((use_machine(c) + 1) / 2);
}
return ans;
}
if (b.size() >= M)
{
int ans = a.size();
for (; i < n; )
{
vector <int> c;
for (int j = 0; j < b.size() && i < n; j++, i++)
{
c.pb(i);
c.pb(b[j]);
}
ans += ((use_machine(c) + 1) / 2);
}
return ans;
}
return a.size();
}
Compilation message
mushrooms.cpp:14:1: warning: multi-line comment [-Wcomment]
14 | //#define FMT_TO_STR(fmt, result) va_list vargs; va_start(vargs, fmt); \
| ^
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:172:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for (int j = 0; j < a.size() && i < n; j++, i++)
| ~~^~~~~~~~~~
mushrooms.cpp:187:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for (int j = 0; j < b.size() && i < n; j++, i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 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 |
304 KB |
Output is correct |
| 6 |
Correct |
3 ms |
208 KB |
Output is correct |
| 7 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 8 |
Partially correct |
9 ms |
208 KB |
Output is partially correct |
| 9 |
Partially correct |
9 ms |
208 KB |
Output is partially correct |
| 10 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 11 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 12 |
Partially correct |
7 ms |
308 KB |
Output is partially correct |
| 13 |
Partially correct |
7 ms |
208 KB |
Output is partially correct |
| 14 |
Correct |
4 ms |
208 KB |
Output is correct |
| 15 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 16 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 17 |
Correct |
4 ms |
208 KB |
Output is correct |
| 18 |
Partially correct |
8 ms |
304 KB |
Output is partially correct |
| 19 |
Partially correct |
11 ms |
208 KB |
Output is partially correct |
| 20 |
Partially correct |
8 ms |
312 KB |
Output is partially correct |
| 21 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 22 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 23 |
Partially correct |
10 ms |
308 KB |
Output is partially correct |
| 24 |
Correct |
6 ms |
208 KB |
Output is correct |
| 25 |
Partially correct |
11 ms |
208 KB |
Output is partially correct |
| 26 |
Partially correct |
15 ms |
208 KB |
Output is partially correct |
| 27 |
Partially correct |
7 ms |
208 KB |
Output is partially correct |
| 28 |
Partially correct |
13 ms |
208 KB |
Output is partially correct |
| 29 |
Partially correct |
14 ms |
208 KB |
Output is partially correct |
| 30 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 31 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 32 |
Partially correct |
6 ms |
208 KB |
Output is partially correct |
| 33 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 34 |
Partially correct |
7 ms |
208 KB |
Output is partially correct |
| 35 |
Partially correct |
9 ms |
208 KB |
Output is partially correct |
| 36 |
Partially correct |
8 ms |
304 KB |
Output is partially correct |
| 37 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 38 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 39 |
Partially correct |
11 ms |
208 KB |
Output is partially correct |
| 40 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 41 |
Partially correct |
9 ms |
208 KB |
Output is partially correct |
| 42 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 43 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 44 |
Partially correct |
6 ms |
316 KB |
Output is partially correct |
| 45 |
Partially correct |
11 ms |
308 KB |
Output is partially correct |
| 46 |
Partially correct |
11 ms |
208 KB |
Output is partially correct |
| 47 |
Partially correct |
11 ms |
208 KB |
Output is partially correct |
| 48 |
Partially correct |
9 ms |
308 KB |
Output is partially correct |
| 49 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 50 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 51 |
Partially correct |
11 ms |
308 KB |
Output is partially correct |
| 52 |
Partially correct |
9 ms |
208 KB |
Output is partially correct |
| 53 |
Partially correct |
8 ms |
208 KB |
Output is partially correct |
| 54 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 55 |
Partially correct |
9 ms |
304 KB |
Output is partially correct |
| 56 |
Partially correct |
12 ms |
308 KB |
Output is partially correct |
| 57 |
Partially correct |
10 ms |
308 KB |
Output is partially correct |
| 58 |
Partially correct |
10 ms |
208 KB |
Output is partially correct |
| 59 |
Partially correct |
9 ms |
208 KB |
Output is partially correct |
| 60 |
Partially correct |
11 ms |
308 KB |
Output is partially correct |
| 61 |
Partially correct |
10 ms |
308 KB |
Output is partially correct |
| 62 |
Correct |
1 ms |
208 KB |
Output is correct |
| 63 |
Correct |
0 ms |
208 KB |
Output is correct |
| 64 |
Correct |
1 ms |
208 KB |
Output is correct |
| 65 |
Correct |
0 ms |
208 KB |
Output is correct |
| 66 |
Correct |
1 ms |
208 KB |
Output is correct |
| 67 |
Correct |
1 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 |
1 ms |
208 KB |
Output is correct |
| 71 |
Correct |
1 ms |
208 KB |
Output is correct |
| 72 |
Correct |
1 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 |
1 ms |
208 KB |
Output is correct |
| 76 |
Correct |
1 ms |
208 KB |
Output is correct |
| 77 |
Correct |
1 ms |
208 KB |
Output is correct |
| 78 |
Correct |
1 ms |
208 KB |
Output is correct |
| 79 |
Correct |
1 ms |
208 KB |
Output is correct |
| 80 |
Correct |
1 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 |
1 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 |
