#include"mushrooms.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
inline int query(initializer_list<int>v)
{
vector<int>nv;
for(int t:v)
nv.eb(t);
return use_machine(nv);
}
inline void get(int o,int p,vector<int>&av,vector<int>&bv)
{
int i=av[0],j=av[1];
int c=query({i,o,j,p});
(c/2==0?av:bv).eb(o);
(c%2==0?av:bv).eb(p);
return;
}
inline void get(int o,int p,int q,int r,int s,vector<int>&av,vector<int>&bv)
{
int i=av[0],j=av[1],k=av[2];
int x=bv[0];
int c=query({o,i,p,j,q,k,r,s});
int p2=0;
if(c==0)
p2=0;
else if(c==1)
{
int c2=query({i,r,j,s});
if(c2==0)
p2=1;
else if(c2==1)
p2=16;
else if(c2==3)
p2=24;
}
else if(c==2)
{
int c2=query({o,i,s,j,r,k,q});
if(c2==0)
p2=2;
else if(c2==1)
p2=4;
else if(c2==2)
p2=8;
else if(c2==3)
p2=17;
else if(c2==4)
p2=25;
}
else if(c==3)
{
int c2=query({q,p,i,s,j,r,o,x});
if(c2==1)
p2=9;
else if(c2==2)
p2=5;
else if(c2==3)
p2=3;
else if(c2==4)
p2=20;
else if(c2==5)
p2=18;
else if(c2==6)
p2=28;
else if(c2==7)
p2=26;
}
else if(c==4)
{
int c2=query({r,i,o,j,s,k,q,p,x});
if(c2==1)
p2=6;
else if(c2==3)
p2=10;
else if(c2==4)
p2=12;
else if(c2==5)
p2=19;
else if(c2==6)
p2=27;
else if(c2==7)
p2=21;
else if(c2==8)
p2=29;
}
else if(c==5)
{
int c2=query({q,i,r,j,s,k,p,o});
if(c2==2)
p2=7;
else if(c2==3)
p2=11;
else if(c2==4)
p2=13;
else if(c2==5)
p2=22;
else if(c2==7)
p2=30;
}
else if(c==6)
{
int c2=query({i,r,j,s});
if(c2==1)
p2=23;
else if(c2==2)
p2=14;
else
p2=31;
}
else
p2=15;
(p2>>0&1?bv:av).eb(o);
(p2>>1&1?bv:av).eb(p);
(p2>>2&1?bv:av).eb(q);
(p2>>3&1?bv:av).eb(r);
(p2>>4&1?bv:av).eb(s);
return;
}
int count_mushrooms(int n)
{
if(n<440)
{
int c=1;
for(int i=1;i<n;i+=2)
{
if(i+1==n)
c+=1-query({0,i});
else
c+=2-query({i,0,i+1});
}
return c;
}
vector<int>av(1,0),bv;
{
int c=query({0,1,2,3});
if(c==0)
av.eb(1),av.eb(2),av.eb(3);
else if(c==1)
{
int c2=query({0,3,1,2});
if(c2==2)
av.eb(1),av.eb(2),bv.eb(3);
else if(c2==3)
av.eb(1),bv.eb(2),bv.eb(3);
else if(c2==1)
bv.eb(1),bv.eb(2),bv.eb(3);
}
else if(c==2)
{
int c2=query({1,0,2,3});
if(c2==2)
av.eb(1),bv.eb(2),av.eb(3);
else if(c2==3)
bv.eb(1),bv.eb(2),av.eb(3);
else if(c2==1)
bv.eb(1),av.eb(2),av.eb(3);
}
else
bv.eb(1),av.eb(2),bv.eb(3);
}
if(av.size()>bv.size())
get(4,5,av,bv);
else
get(4,5,bv,av);
const int size=92;
for(int i=av.size()+bv.size();(int)av.size()<size&&(int)bv.size()<size;i=av.size()+bv.size())
{
if(av.empty())
get(i,i+1,bv,av);
else if(bv.empty())
get(i,i+1,av,bv);
else if(av.size()>bv.size())
get(i,i+1,i+2,i+3,i+4,av,bv);
else
get(i,i+1,i+2,i+3,i+4,bv,av);
if((int)max(av.size(),bv.size())*1.2-(int)min(av.size(),bv.size())-0.2>=size)
break;
}
int c=av.size();
for(int i=av.size()+bv.size();i<n;)
{
if(av.size()>bv.size())
{
int sz=av.size();
vector<int>qv;
for(int j=i;j<i+sz&&j<n;j++)
qv.eb(j),qv.eb(av[j-i]);
int c2=use_machine(qv);
(c2%2==0?av:bv).eb(i);
c+=(int)qv.size()/2-(c2+1)/2;
i+=sz;
}
else
{
int sz=bv.size();
vector<int>qv;
for(int j=i;j<i+sz&&j<n;j++)
qv.eb(j),qv.eb(bv[j-i]);
int c2=use_machine(qv);
(c2%2==1?bv:av).eb(i);
c+=(c2+1)/2;
i+=sz;
}
}
return c;
}
| # |
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 |
256 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
256 KB |
Answer is not correct. |
| 7 |
Halted |
0 ms |
0 KB |
- |
