#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 10;
const int T = 3;
vector<int> ask[200];
int res[200][M];
void pre(){
ask[1] = {0,3,1,4,2,5,6,7,8,9};
res[1][0] = 2;
res[1][1] = 3;
ask[3] = {0,1,2,7,5,8,6};
res[3][0] = 4;
res[3][1] = 5;
res[3][2] = 6;
res[3][3] = 7;
res[3][4] = 8;
res[1][2] = 9;
ask[9] = {5,0,6,1,7,2,8};
res[9][0] = 10;
ask[10] = {0,1,2,3};
res[10][0] = 11;
res[10][1] = 12;
res[9][1] = 13;
ask[13] = {0,1,2,5};
res[13][0] = 14;
res[13][1] = 15;
res[9][2] = 16;
ask[16] = {0,1,2,6};
res[16][0] = 17;
res[16][1] = 18;
res[9][3] = 19;
ask[19] = {0,1,2,5};
res[19][0] = 20;
res[19][1] = 21;
res[9][4] = 22;
res[9][5] = 23;
ask[23] = {0,1,2,5};
res[23][0] = 24;
res[23][1] = 25;
res[9][6] = 26;
res[1][3] = 27;
ask[27] = {0,5,1,6,2,7};
res[27][0] = 28;
ask[28] = {0,1,3,2,8};
res[28][0] = 29;
res[28][1] = 30;
res[28][2] = 31;
res[28][3] = 32;
res[27][1] = 33;
ask[33] = {0,1,2,3,4};
res[33][0] = 34;
res[33][1] = 35;
res[33][2] = 36;
res[27][2] = 37;
ask[37] = {0,1,5,2,8};
res[37][0] = 38;
res[37][1] = 39;
res[37][2] = 40;
res[37][3] = 41;
res[27][3] = 42;
ask[42] = {0,1,3,2,6,4};
res[42][0] = 43;
res[42][1] = 44;
res[42][2] = 45;
res[42][4] = 46;
res[27][4] = 47;
ask[47] = {0,1,2,8};
res[47][0] = 48;
res[47][1] = 49;
res[27][5] = 50;
ask[50] = {0,1,2,3,4};
res[50][0] = 51;
res[50][1] = 52;
res[50][2] = 53;
res[1][4] = 54;
ask[54] = {0,5,7,1,6,2,3,4};
res[54][1] = 55;
ask[55] = {0,1,2,3};
res[55][0] = 56;
res[55][1] = 57;
res[54][2] = 58;
ask[58] = {3,0,5,1,7,2,8};
res[58][1] = 59;
res[58][2] = 60;
res[58][3] = 61;
res[58][4] = 62;
res[58][5] = 63;
res[54][3] = 64;
ask[64] = {5,0,1,6,2,4,8};
res[64][1] = 65;
res[64][2] = 66;
res[64][3] = 67;
res[64][4] = 68;
res[54][4] = 69;
ask[69] = {0,1,8,2,5,7};
res[69][0] = 70;
res[69][1] = 71;
res[69][2] = 72;
res[69][3] = 73;
res[69][4] = 74;
res[54][5] = 75;
ask[75] = {0,7,1,8,2,5};
res[75][1] = 76;
res[75][2] = 77;
res[75][3] = 78;
res[75][4] = 79;
res[75][5] = 80;
res[54][6] = 81;
ask[81] = {0,7,1,8,2,5};
res[81][1] = 82;
res[81][2] = 83;
res[81][3] = 84;
res[81][4] = 85;
res[81][5] = 86;
res[1][5] = 87;
ask[87] = {3,9,5,7,0,4,1,8,2,6};
res[87][1] = 88;
res[87][2] = 89;
ask[89] = {0,1,3,2,5,7};
res[89][1] = 90;
res[89][2] = 91;
res[89][3] = 92;
res[89][4] = 93;
res[87][3] = 94;
ask[94] = {0,1,5,2,7};
res[94][0] = 95;
res[94][1] = 96;
res[94][2] = 97;
res[94][3] = 98;
res[87][4] = 99;
ask[99] = {0,1,3,2,7,5};
res[99][1] = 100;
res[99][2] = 101;
res[99][3] = 102;
res[99][4] = 103;
res[87][5] = 104;
ask[104] = {0,1,2,7,3,5};
res[104][0] = 105;
res[104][1] = 106;
res[104][2] = 107;
res[104][3] = 108;
res[87][6] = 109;
ask[109] = {0,3,1,5,2,7};
res[109][1] = 110;
res[109][2] = 111;
res[109][3] = 112;
res[109][5] = 113;
res[87][7] = 114;
ask[114] = {0,1,2,3,5,7};
res[114][0] = 115;
res[114][1] = 116;
res[114][2] = 117;
res[114][3] = 118;
res[87][8] = 119;
res[1][6] = 120;
ask[120] = {0,1,8,2,6,3,4,5};
res[120][1] = 121;
ask[121] = {0,1,6,2,7};
res[121][0] = 122;
res[121][1] = 123;
res[121][2] = 124;
res[121][3] = 125;
res[120][2] = 126;
ask[126] = {0,1,6,2,7};
res[126][1] = 127;
res[126][2] = 128;
res[126][3] = 129;
res[120][3] = 130;
ask[130] = {0,1,4,2,7,3};
res[130][1] = 131;
res[130][2] = 132;
res[130][3] = 133;
res[130][4] = 134;
res[120][4] = 135;
ask[135] = {0,1,6,2,7};
res[135][0] = 136;
res[135][1] = 137;
res[135][2] = 138;
res[135][3] = 139;
res[120][5] = 140;
ask[140] = {0,1,3,2,7,6};
res[140][1] = 141;
res[140][2] = 142;
res[140][3] = 143;
res[140][4] = 144;
res[120][6] = 145;
res[1][7] = 146;
ask[146] = {0,1,6,2,3,5,4,8,7};
res[146][1] = 147;
res[146][2] = 148;
ask[148] = {0,1,2,8};
res[148][0] = 149;
res[148][1] = 150;
res[146][3] = 151;
ask[151] = {0,1,2,3};
res[151][0] = 152;
res[151][1] = 153;
res[146][4] = 154;
ask[154] = {0,1,2,8};
res[154][0] = 155;
res[154][1] = 156;
res[146][5] = 157;
ask[157] = {0,1,2,5};
res[157][0] = 158;
res[157][1] = 159;
res[146][6] = 160;
ask[160] = {0,1,2,8};
res[160][0] = 161;
res[160][1] = 162;
res[146][7] = 163;
res[1][8] = 164;
ask[164] = {0,1,3,6,8,2,5,7};
res[164][2] = 165;
res[164][3] = 166;
res[164][4] = 167;
res[164][5] = 168;
res[164][6] = 169;
res[1][9] = 170;
}
int val[200005];
int get(int pos){
return val[pos] = use_machine({0, pos});
}
void get(vector<int> positions){
// assumption : positions[0], positions[1], positions[2] have the same value
vector<int> states;
for(int i = 0; i < (1 << M); i += (1 << T)) states.push_back(i);
int node = 1;
int asked = 0;
while((int) states.size() > 1){
assert(!ask[node].empty());
vector<int> x;
for(int u : ask[node]) x.push_back(positions[u]);
int R = use_machine(x);
asked++;
vector<int> new_states;
for(auto it : states){
int r = 0;
for(int j = 0; j + 1 < (int) ask[node].size(); j++) r += (it >> ask[node][j] & 1) != (it >> ask[node][j + 1] & 1);
if(r == R) new_states.push_back(it);
}
node = res[node][R];
assert(node != 0);
states = new_states;
}
assert(asked <= 3);
int mask = states[0];
for(int i = 0; i < (int)positions.size(); i++) val[positions[i]] = (mask >> i & 1) ^ val[positions[0]];
}
const int K = 185;
int count_mushrooms(int N) {
pre();
int n = min(N, K);
vector<vector<int>> w(2);
w[0] = {0};
int done = 0;
if(n >= 5){
for(int i = 1; i < 5; i++){
get(i);
w[val[i]].push_back(i);
done = i;
}
}
vector<int> f = (int)w[0].size() > (int) w[1].size() ? w[0] : w[1];
f.resize(3);
// int n = N;
// for(int j = 1; j < N; j++) get(j);
for(int i = done + 1; i < n; i += M - 3){
int st = i, en = i + M - 2;
if(en < n){
vector<int> positions = f;
for(int j = st; j <= en; j++) positions.push_back(j);
get(positions);
} else{
for(int j = st; j < n; j++) get(j);
}
}
int curr = n - accumulate(val, val + n, 0);
if(n == N) return curr;
vector<vector<int>> where(2);
for(int i = 0; i < n; i++) where[val[i]].push_back(i);
int i = n;
while(i < N){
int id = (int)where[1].size() > (int) where[0].size();
int R = where[id].size();
int st = i, en = min(N - 1, i + R - 1);
vector<int> positions;
for(int j = 0; j <= en - st; j++){
positions.push_back(where[id][j]);
positions.push_back(st + j);
}
int V = use_machine(positions);
if(V % 2 == 1){
if(id == 1){
where[0].push_back(positions.back());
curr++;
}
else where[1].push_back(positions.back());
} else{
if(id == 0){
where[0].push_back(positions.back());
curr++;
} else{
where[1].push_back(positions.back());
}
}
V /= 2;
if(id == 1) curr += V;
else curr += en - st - V;
i = en + 1;
}
return curr;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
7 ms |
384 KB |
Output is correct |
| 8 |
Correct |
7 ms |
408 KB |
Output is correct |
| 9 |
Correct |
7 ms |
384 KB |
Output is correct |
| 10 |
Correct |
8 ms |
384 KB |
Output is correct |
| 11 |
Correct |
7 ms |
384 KB |
Output is correct |
| 12 |
Correct |
8 ms |
384 KB |
Output is correct |
| 13 |
Correct |
7 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 16 |
Partially correct |
8 ms |
384 KB |
Output is partially correct |
| 17 |
Correct |
6 ms |
384 KB |
Output is correct |
| 18 |
Correct |
8 ms |
384 KB |
Output is correct |
| 19 |
Partially correct |
8 ms |
384 KB |
Output is partially correct |
| 20 |
Correct |
6 ms |
412 KB |
Output is correct |
| 21 |
Correct |
9 ms |
384 KB |
Output is correct |
| 22 |
Correct |
9 ms |
400 KB |
Output is correct |
| 23 |
Correct |
7 ms |
384 KB |
Output is correct |
| 24 |
Correct |
6 ms |
404 KB |
Output is correct |
| 25 |
Partially correct |
8 ms |
384 KB |
Output is partially correct |
| 26 |
Correct |
7 ms |
384 KB |
Output is correct |
| 27 |
Partially correct |
8 ms |
404 KB |
Output is partially correct |
| 28 |
Correct |
9 ms |
384 KB |
Output is correct |
| 29 |
Partially correct |
8 ms |
408 KB |
Output is partially correct |
| 30 |
Partially correct |
8 ms |
412 KB |
Output is partially correct |
| 31 |
Correct |
10 ms |
384 KB |
Output is correct |
| 32 |
Partially correct |
10 ms |
400 KB |
Output is partially correct |
| 33 |
Correct |
8 ms |
400 KB |
Output is correct |
| 34 |
Correct |
7 ms |
384 KB |
Output is correct |
| 35 |
Partially correct |
8 ms |
384 KB |
Output is partially correct |
| 36 |
Partially correct |
8 ms |
384 KB |
Output is partially correct |
| 37 |
Partially correct |
8 ms |
384 KB |
Output is partially correct |
| 38 |
Correct |
7 ms |
408 KB |
Output is correct |
| 39 |
Partially correct |
7 ms |
360 KB |
Output is partially correct |
| 40 |
Partially correct |
7 ms |
384 KB |
Output is partially correct |
| 41 |
Partially correct |
7 ms |
428 KB |
Output is partially correct |
| 42 |
Partially correct |
7 ms |
404 KB |
Output is partially correct |
| 43 |
Correct |
9 ms |
408 KB |
Output is correct |
| 44 |
Correct |
8 ms |
396 KB |
Output is correct |
| 45 |
Partially correct |
8 ms |
384 KB |
Output is partially correct |
| 46 |
Partially correct |
11 ms |
384 KB |
Output is partially correct |
| 47 |
Correct |
7 ms |
384 KB |
Output is correct |
| 48 |
Partially correct |
11 ms |
404 KB |
Output is partially correct |
| 49 |
Correct |
7 ms |
400 KB |
Output is correct |
| 50 |
Partially correct |
8 ms |
360 KB |
Output is partially correct |
| 51 |
Partially correct |
9 ms |
360 KB |
Output is partially correct |
| 52 |
Partially correct |
9 ms |
400 KB |
Output is partially correct |
| 53 |
Partially correct |
13 ms |
384 KB |
Output is partially correct |
| 54 |
Partially correct |
9 ms |
384 KB |
Output is partially correct |
| 55 |
Correct |
8 ms |
384 KB |
Output is correct |
| 56 |
Partially correct |
8 ms |
404 KB |
Output is partially correct |
| 57 |
Partially correct |
14 ms |
384 KB |
Output is partially correct |
| 58 |
Partially correct |
7 ms |
384 KB |
Output is partially correct |
| 59 |
Correct |
9 ms |
400 KB |
Output is correct |
| 60 |
Correct |
11 ms |
384 KB |
Output is correct |
| 61 |
Correct |
7 ms |
404 KB |
Output is correct |
| 62 |
Correct |
1 ms |
384 KB |
Output is correct |
| 63 |
Correct |
1 ms |
384 KB |
Output is correct |
| 64 |
Correct |
0 ms |
384 KB |
Output is correct |
| 65 |
Correct |
0 ms |
384 KB |
Output is correct |
| 66 |
Correct |
1 ms |
384 KB |
Output is correct |
| 67 |
Correct |
1 ms |
384 KB |
Output is correct |
| 68 |
Correct |
1 ms |
384 KB |
Output is correct |
| 69 |
Correct |
1 ms |
384 KB |
Output is correct |
| 70 |
Correct |
1 ms |
384 KB |
Output is correct |
| 71 |
Correct |
0 ms |
384 KB |
Output is correct |
| 72 |
Correct |
0 ms |
384 KB |
Output is correct |
| 73 |
Correct |
1 ms |
384 KB |
Output is correct |
| 74 |
Correct |
1 ms |
360 KB |
Output is correct |
| 75 |
Correct |
1 ms |
384 KB |
Output is correct |
| 76 |
Correct |
1 ms |
384 KB |
Output is correct |
| 77 |
Correct |
1 ms |
384 KB |
Output is correct |
| 78 |
Correct |
0 ms |
384 KB |
Output is correct |
| 79 |
Correct |
1 ms |
308 KB |
Output is correct |
| 80 |
Correct |
1 ms |
384 KB |
Output is correct |
| 81 |
Correct |
1 ms |
384 KB |
Output is correct |
| 82 |
Correct |
1 ms |
384 KB |
Output is correct |
| 83 |
Correct |
1 ms |
384 KB |
Output is correct |
| 84 |
Correct |
1 ms |
384 KB |
Output is correct |
| 85 |
Correct |
1 ms |
384 KB |
Output is correct |
| 86 |
Correct |
0 ms |
384 KB |
Output is correct |
| 87 |
Correct |
1 ms |
384 KB |
Output is correct |
| 88 |
Correct |
1 ms |
384 KB |
Output is correct |
| 89 |
Correct |
0 ms |
384 KB |
Output is correct |
| 90 |
Correct |
1 ms |
384 KB |
Output is correct |
| 91 |
Correct |
0 ms |
384 KB |
Output is correct |
