#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include "mushrooms.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
float pi=3.14159265358979323846;
int prep=77;
int count_mushrooms(int n)
{
vector<int> unknown,red={0},blue,qvec;
for(int i=1;i<n;i++)
unknown.eb(i);
mt19937 rng(time);
uniform_int_distribution<int> rng2(0,1);
shuffle(all(unknown),rng);
int res=1;
while(size(unknown)>1&&prep>0)
{
prep--;
qvec.clear();
if(max(size(red),size(blue))==1)
{
qvec.eb(red[0]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==1)
blue.eb(qvec.back());
else
red.eb(qvec.back()),res++;
}
else
if(min(size(red),size(blue))<2)
{
if(size(red)>1)
{
qvec.eb(red[0]);
qvec.eb(unknown.back()),unknown.pop_back();
qvec.eb(red[1]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==0)
res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
else
if(ans==1)
res+=1,red.eb(qvec[1]),blue.eb(qvec[3]);
else
if(ans==2)
res+=1,red.eb(qvec[3]),blue.eb(qvec[1]);
else
if(ans==3)
blue.eb(qvec[1]),blue.eb(qvec[3]);
}
else
{
qvec.eb(blue[0]);
qvec.eb(unknown.back()),unknown.pop_back();
qvec.eb(blue[1]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==0)
blue.eb(qvec[1]),blue.eb(qvec[3]);
else
if(ans==1)
res+=1,blue.eb(qvec[1]),red.eb(qvec[3]);
else
if(ans==2)
res+=1,blue.eb(qvec[3]),red.eb(qvec[1]);
else
if(ans==3)
res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
}
}
else
{
if(rng2(rng)&1)
{
qvec.eb(red[0]);
qvec.eb(unknown.back()),unknown.pop_back();
qvec.eb(red[1]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==0)
res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
else
if(ans==1)
res+=1,red.eb(qvec[1]),blue.eb(qvec[3]);
else
if(ans==2)
res+=1,red.eb(qvec[3]),blue.eb(qvec[1]);
else
if(ans==3)
blue.eb(qvec[1]),blue.eb(qvec[3]);
}
else
{
qvec.eb(blue[0]);
qvec.eb(unknown.back()),unknown.pop_back();
qvec.eb(blue[1]);
qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans==0)
blue.eb(qvec[1]),blue.eb(qvec[3]);
else
if(ans==1)
res+=1,blue.eb(qvec[1]),red.eb(qvec[3]);
else
if(ans==2)
res+=1,blue.eb(qvec[3]),red.eb(qvec[1]);
else
if(ans==3)
res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
}
}
}
while(size(unknown))
{
qvec.clear();
if(size(red)>size(blue))
{
int p=0;
while(p<size(red)&&size(unknown)>0)
qvec.eb(red[p++]),qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans&1)
blue.eb(qvec.back()),ans++;
else
red.eb(qvec.back());
ans/=2;
res+=p-ans;
}
else
{
int p=0;
while(p<size(blue)&&size(unknown)>0)
qvec.eb(blue[p++]),qvec.eb(unknown.back()),unknown.pop_back();
int ans=use_machine(qvec);
if(ans&1)
red.eb(qvec.back()),ans++;
else
blue.eb(qvec.back());
ans/=2;
res+=ans;
}
}
return res;
}
Compilation message
mushrooms.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
mushrooms.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
360 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
10 ms |
512 KB |
Output is correct |
| 8 |
Correct |
10 ms |
512 KB |
Output is correct |
| 9 |
Correct |
8 ms |
512 KB |
Output is correct |
| 10 |
Correct |
8 ms |
492 KB |
Output is correct |
| 11 |
Partially correct |
9 ms |
512 KB |
Output is partially correct |
| 12 |
Correct |
10 ms |
600 KB |
Output is correct |
| 13 |
Correct |
9 ms |
492 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Partially correct |
11 ms |
512 KB |
Output is partially correct |
| 16 |
Partially correct |
10 ms |
488 KB |
Output is partially correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
10 ms |
512 KB |
Output is correct |
| 19 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 20 |
Correct |
9 ms |
564 KB |
Output is correct |
| 21 |
Correct |
12 ms |
512 KB |
Output is correct |
| 22 |
Partially correct |
7 ms |
512 KB |
Output is partially correct |
| 23 |
Correct |
10 ms |
512 KB |
Output is correct |
| 24 |
Correct |
6 ms |
384 KB |
Output is correct |
| 25 |
Partially correct |
11 ms |
512 KB |
Output is partially correct |
| 26 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 27 |
Partially correct |
7 ms |
512 KB |
Output is partially correct |
| 28 |
Partially correct |
9 ms |
512 KB |
Output is partially correct |
| 29 |
Partially correct |
9 ms |
512 KB |
Output is partially correct |
| 30 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 31 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 32 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 33 |
Partially correct |
11 ms |
512 KB |
Output is partially correct |
| 34 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 35 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 36 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 37 |
Partially correct |
7 ms |
512 KB |
Output is partially correct |
| 38 |
Partially correct |
9 ms |
512 KB |
Output is partially correct |
| 39 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 40 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 41 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 42 |
Partially correct |
9 ms |
512 KB |
Output is partially correct |
| 43 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 44 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 45 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 46 |
Partially correct |
9 ms |
512 KB |
Output is partially correct |
| 47 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 48 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 49 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 50 |
Partially correct |
9 ms |
512 KB |
Output is partially correct |
| 51 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 52 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 53 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 54 |
Partially correct |
8 ms |
488 KB |
Output is partially correct |
| 55 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 56 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 57 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 58 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 59 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 60 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 61 |
Partially correct |
12 ms |
512 KB |
Output is partially correct |
| 62 |
Correct |
0 ms |
256 KB |
Output is correct |
| 63 |
Correct |
0 ms |
256 KB |
Output is correct |
| 64 |
Correct |
1 ms |
256 KB |
Output is correct |
| 65 |
Correct |
1 ms |
256 KB |
Output is correct |
| 66 |
Correct |
1 ms |
256 KB |
Output is correct |
| 67 |
Correct |
1 ms |
256 KB |
Output is correct |
| 68 |
Correct |
1 ms |
416 KB |
Output is correct |
| 69 |
Correct |
1 ms |
256 KB |
Output is correct |
| 70 |
Correct |
1 ms |
256 KB |
Output is correct |
| 71 |
Correct |
1 ms |
256 KB |
Output is correct |
| 72 |
Correct |
1 ms |
256 KB |
Output is correct |
| 73 |
Correct |
1 ms |
256 KB |
Output is correct |
| 74 |
Correct |
0 ms |
256 KB |
Output is correct |
| 75 |
Correct |
1 ms |
256 KB |
Output is correct |
| 76 |
Correct |
1 ms |
256 KB |
Output is correct |
| 77 |
Correct |
0 ms |
256 KB |
Output is correct |
| 78 |
Correct |
1 ms |
256 KB |
Output is correct |
| 79 |
Correct |
1 ms |
256 KB |
Output is correct |
| 80 |
Correct |
1 ms |
256 KB |
Output is correct |
| 81 |
Correct |
1 ms |
256 KB |
Output is correct |
| 82 |
Correct |
1 ms |
256 KB |
Output is correct |
| 83 |
Correct |
1 ms |
256 KB |
Output is correct |
| 84 |
Correct |
0 ms |
256 KB |
Output is correct |
| 85 |
Correct |
1 ms |
288 KB |
Output is correct |
| 86 |
Correct |
0 ms |
256 KB |
Output is correct |
| 87 |
Correct |
1 ms |
256 KB |
Output is correct |
| 88 |
Correct |
1 ms |
256 KB |
Output is correct |
| 89 |
Correct |
0 ms |
256 KB |
Output is correct |
| 90 |
Correct |
1 ms |
256 KB |
Output is correct |
| 91 |
Correct |
1 ms |
384 KB |
Output is correct |
