#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
void wypiszvector(vector<int>&vec){
printf("{");
for(auto j: vec)printf("%d,", j);
printf("}\n");
}
const int stala = 6;
int maska[83] = {0,0,0,4,8,59,9,43,41,0,0,63,1,0,32,2,16,0,33,47,35,0,12,18,34,0,45,13,51,50,0,0,24,40,26,27,58,0,36,5,37,55,39,0,10,42,11,57,25,0,20,6,22,38,54,0,0,46,17,44,19,0,3,62,61,0,49,48,14,0,31,29,30,28,15,0,56,7,52,23,53,21,60,};
vector<int>zapytanie[83] = {{4,1,6,2,5,0,3,},{},{2,4,5,6,0,1,3,},{},{},{},{},{},{},{1,2,3,5,4,6,0,},{3,6,4,1,2,},{},{},{2,5,1,3,0,4,},{},{},{},{4,6,5,3,2,0,1,},{},{},{},{3,5,2,0,1,6,},{},{},{},{3,5,0,1,4,6,},{},{},{},{},{0,3,1,2,5,4,},{1,6,0,2,3,5,},{},{},{},{},{},{5,1,4,2,0,6,},{},{},{},{},{},{4,3,5,0,1,6,},{},{},{},{},{},{1,6,4,2,0,5,},{},{},{},{},{},{5,1,0,3,6,4,},{0,5,6,1,3,2,4,},{},{},{},{},{2,5,6,0,3,},{},{},{},{1,6,4,2,0,3,},{},{},{},{4,1,5,6,0,3,2,},{},{},{},{},{},{6,5,4,3,2,1,0,},{},{},{},{},{},{},{},};
vector<int>graf[83] = {{1,2,9,30,55,75,82,},{},{-1,3,4,5,6,7,8,},{},{},{},{},{},{},{-1,10,13,17,21,25,29,},{11,-1,12,},{},{},{14,15,16,},{},{},{},{-1,-1,-1,18,19,20,},{},{},{},{-1,22,23,24,},{},{},{},{-1,-1,26,27,-1,28,},{},{},{},{},{-1,31,37,43,49,},{-1,32,33,34,35,36,},{},{},{},{},{},{-1,38,39,40,41,42,},{},{},{},{},{},{-1,44,45,46,47,48,},{},{},{},{},{},{-1,50,51,52,53,54,},{},{},{},{},{},{-1,56,61,65,69,74,},{-1,-1,-1,57,58,59,60,},{},{},{},{},{-1,62,63,64,},{},{},{},{-1,66,67,68,},{},{},{},{-1,-1,70,71,72,73,},{},{},{},{},{},{-1,76,77,78,79,80,81,},{},{},{},{},{},{},{},};
vector<int>A[2];
int Ac[2];
int it;
int count_mushrooms1(int n){
while(it<n){
// printf("it = %d\n", it);
vector<int>pom;
bool czy = 0;
if(A[1].size()>A[0].size())czy = 1;
int pom1 = 0;
while(it<n && pom.size()<2*A[czy].size()){
pom.push_back(A[czy][pom1++]);
pom.push_back(it);
it++;
}
int ans = use_machine(pom);
// printf("vec: = ");for(auto j: pom)printf("%d ", j);printf("\n");
// printf("ans = %d\n", ans);
if(ans%2==0)
A[czy].push_back(it-1);
else
A[!czy].push_back(it-1);
Ac[!czy]+=(ans+1)/2;
Ac[czy]+=pom1-(ans+1)/2;
if(pom1==2){
if(ans<2)
A[czy].push_back(it-2);
else
A[!czy].push_back(it-2);
}
}
// printf("res = %d\n", Ac[0]);
return Ac[0];
}
int count_mushrooms(int n){
A[0].push_back(0);
it = 1;
Ac[0] = 1;
Ac[1] = 0;
for(int ile=0;ile<40;ile++)
{
if(n<=stala+it)
return count_mushrooms1(n);
int x = 0;
while(graf[x].size()>0){
vector<int>pom;
pom = zapytanie[x];
for(auto &j: pom)
if(j>0)
j+=ile*stala;
int c = use_machine(pom);
// wypiszvector(zapytanie[x]);
x = graf[x][c];
}
x = maska[x];
for(int i=0;i<stala;i++){
A[(x>>i)&1].push_back(ile*stala+i+1);
Ac[(x>>i)&1]++;
}
it+=stala;
}
return count_mushrooms1(n);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
452 KB |
Output is correct |
| 6 |
Correct |
1 ms |
456 KB |
Output is correct |
| 7 |
Correct |
3 ms |
460 KB |
Output is correct |
| 8 |
Correct |
3 ms |
464 KB |
Output is correct |
| 9 |
Correct |
3 ms |
464 KB |
Output is correct |
| 10 |
Correct |
4 ms |
456 KB |
Output is correct |
| 11 |
Partially correct |
4 ms |
460 KB |
Output is partially correct |
| 12 |
Correct |
4 ms |
456 KB |
Output is correct |
| 13 |
Correct |
4 ms |
460 KB |
Output is correct |
| 14 |
Correct |
2 ms |
708 KB |
Output is correct |
| 15 |
Partially correct |
4 ms |
464 KB |
Output is partially correct |
| 16 |
Partially correct |
4 ms |
460 KB |
Output is partially correct |
| 17 |
Correct |
3 ms |
448 KB |
Output is correct |
| 18 |
Correct |
4 ms |
468 KB |
Output is correct |
| 19 |
Partially correct |
4 ms |
464 KB |
Output is partially correct |
| 20 |
Correct |
4 ms |
456 KB |
Output is correct |
| 21 |
Correct |
4 ms |
452 KB |
Output is correct |
| 22 |
Partially correct |
4 ms |
456 KB |
Output is partially correct |
| 23 |
Correct |
4 ms |
464 KB |
Output is correct |
| 24 |
Correct |
3 ms |
708 KB |
Output is correct |
| 25 |
Partially correct |
4 ms |
460 KB |
Output is partially correct |
| 26 |
Partially correct |
4 ms |
460 KB |
Output is partially correct |
| 27 |
Partially correct |
4 ms |
460 KB |
Output is partially correct |
| 28 |
Partially correct |
4 ms |
464 KB |
Output is partially correct |
| 29 |
Partially correct |
4 ms |
452 KB |
Output is partially correct |
| 30 |
Partially correct |
4 ms |
460 KB |
Output is partially correct |
| 31 |
Partially correct |
4 ms |
460 KB |
Output is partially correct |
| 32 |
Partially correct |
4 ms |
456 KB |
Output is partially correct |
| 33 |
Partially correct |
4 ms |
456 KB |
Output is partially correct |
| 34 |
Correct |
4 ms |
468 KB |
Output is correct |
| 35 |
Partially correct |
4 ms |
464 KB |
Output is partially correct |
| 36 |
Partially correct |
4 ms |
456 KB |
Output is partially correct |
| 37 |
Partially correct |
4 ms |
460 KB |
Output is partially correct |
| 38 |
Partially correct |
5 ms |
456 KB |
Output is partially correct |
| 39 |
Partially correct |
4 ms |
464 KB |
Output is partially correct |
| 40 |
Partially correct |
4 ms |
464 KB |
Output is partially correct |
| 41 |
Partially correct |
5 ms |
460 KB |
Output is partially correct |
| 42 |
Partially correct |
4 ms |
456 KB |
Output is partially correct |
| 43 |
Partially correct |
4 ms |
460 KB |
Output is partially correct |
| 44 |
Correct |
4 ms |
460 KB |
Output is correct |
| 45 |
Partially correct |
5 ms |
460 KB |
Output is partially correct |
| 46 |
Correct |
4 ms |
468 KB |
Output is correct |
| 47 |
Correct |
4 ms |
460 KB |
Output is correct |
| 48 |
Correct |
4 ms |
464 KB |
Output is correct |
| 49 |
Correct |
4 ms |
460 KB |
Output is correct |
| 50 |
Correct |
5 ms |
472 KB |
Output is correct |
| 51 |
Correct |
4 ms |
464 KB |
Output is correct |
| 52 |
Correct |
4 ms |
464 KB |
Output is correct |
| 53 |
Correct |
4 ms |
464 KB |
Output is correct |
| 54 |
Correct |
5 ms |
460 KB |
Output is correct |
| 55 |
Correct |
5 ms |
460 KB |
Output is correct |
| 56 |
Correct |
5 ms |
464 KB |
Output is correct |
| 57 |
Correct |
5 ms |
468 KB |
Output is correct |
| 58 |
Correct |
5 ms |
464 KB |
Output is correct |
| 59 |
Correct |
5 ms |
468 KB |
Output is correct |
| 60 |
Correct |
6 ms |
460 KB |
Output is correct |
| 61 |
Correct |
4 ms |
716 KB |
Output is correct |
| 62 |
Correct |
0 ms |
344 KB |
Output is correct |
| 63 |
Correct |
0 ms |
344 KB |
Output is correct |
| 64 |
Correct |
0 ms |
344 KB |
Output is correct |
| 65 |
Correct |
0 ms |
344 KB |
Output is correct |
| 66 |
Correct |
0 ms |
344 KB |
Output is correct |
| 67 |
Correct |
0 ms |
344 KB |
Output is correct |
| 68 |
Correct |
0 ms |
344 KB |
Output is correct |
| 69 |
Correct |
1 ms |
344 KB |
Output is correct |
| 70 |
Correct |
0 ms |
344 KB |
Output is correct |
| 71 |
Correct |
1 ms |
344 KB |
Output is correct |
| 72 |
Correct |
1 ms |
344 KB |
Output is correct |
| 73 |
Correct |
0 ms |
344 KB |
Output is correct |
| 74 |
Correct |
0 ms |
344 KB |
Output is correct |
| 75 |
Correct |
0 ms |
344 KB |
Output is correct |
| 76 |
Correct |
0 ms |
344 KB |
Output is correct |
| 77 |
Correct |
0 ms |
344 KB |
Output is correct |
| 78 |
Correct |
0 ms |
344 KB |
Output is correct |
| 79 |
Correct |
0 ms |
344 KB |
Output is correct |
| 80 |
Correct |
0 ms |
344 KB |
Output is correct |
| 81 |
Correct |
0 ms |
596 KB |
Output is correct |
| 82 |
Correct |
0 ms |
344 KB |
Output is correct |
| 83 |
Correct |
1 ms |
344 KB |
Output is correct |
| 84 |
Correct |
0 ms |
344 KB |
Output is correct |
| 85 |
Correct |
0 ms |
344 KB |
Output is correct |
| 86 |
Correct |
0 ms |
352 KB |
Output is correct |
| 87 |
Correct |
0 ms |
344 KB |
Output is correct |
| 88 |
Correct |
0 ms |
344 KB |
Output is correct |
| 89 |
Correct |
0 ms |
344 KB |
Output is correct |
| 90 |
Correct |
0 ms |
344 KB |
Output is correct |
| 91 |
Correct |
0 ms |
344 KB |
Output is correct |
