oj.uz

Submission #306256

# Submission time Handle Problem Language Result Execution time Memory
306256 2020-09-25T03:42:50 Z gs18115 Counting Mushrooms (IOI20_mushrooms) C++14
100 / 100
 13 ms 384 KB 
#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==5)
			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==2)
			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 if(c2==3)
			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=108;
	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.3-(int)min(av.size(),bv.size())-0.3>=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?av:bv).eb(i);
			c+=(c2+1)/2;
			i+=sz;
		}
	}
	return c;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 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 1 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 7 ms 256 KB Output is correct
8 Correct 7 ms 256 KB Output is correct
9 Correct 6 ms 256 KB Output is correct
10 Correct 7 ms 256 KB Output is correct
11 Correct 7 ms 256 KB Output is correct
12 Correct 7 ms 256 KB Output is correct
13 Correct 7 ms 256 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 7 ms 256 KB Output is correct
16 Correct 7 ms 256 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 7 ms 256 KB Output is correct
19 Correct 7 ms 384 KB Output is correct
20 Correct 7 ms 256 KB Output is correct
21 Correct 6 ms 376 KB Output is correct
22 Correct 7 ms 256 KB Output is correct
23 Correct 7 ms 384 KB Output is correct
24 Correct 4 ms 256 KB Output is correct
25 Correct 7 ms 256 KB Output is correct
26 Correct 7 ms 256 KB Output is correct
27 Correct 10 ms 384 KB Output is correct
28 Correct 8 ms 256 KB Output is correct
29 Correct 9 ms 256 KB Output is correct
30 Correct 9 ms 256 KB Output is correct
31 Correct 7 ms 256 KB Output is correct
32 Correct 7 ms 256 KB Output is correct
33 Correct 7 ms 384 KB Output is correct
34 Correct 6 ms 380 KB Output is correct
35 Correct 7 ms 256 KB Output is correct
36 Correct 8 ms 256 KB Output is correct
37 Correct 7 ms 256 KB Output is correct
38 Correct 7 ms 256 KB Output is correct
39 Correct 8 ms 256 KB Output is correct
40 Correct 9 ms 384 KB Output is correct
41 Correct 6 ms 380 KB Output is correct
42 Correct 7 ms 256 KB Output is correct
43 Correct 9 ms 256 KB Output is correct
44 Correct 7 ms 376 KB Output is correct
45 Correct 7 ms 256 KB Output is correct
46 Correct 8 ms 256 KB Output is correct
47 Correct 7 ms 384 KB Output is correct
48 Correct 7 ms 256 KB Output is correct
49 Correct 7 ms 256 KB Output is correct
50 Correct 8 ms 256 KB Output is correct
51 Correct 7 ms 256 KB Output is correct
52 Correct 7 ms 256 KB Output is correct
53 Correct 7 ms 256 KB Output is correct
54 Correct 10 ms 256 KB Output is correct
55 Correct 7 ms 256 KB Output is correct
56 Correct 8 ms 256 KB Output is correct
57 Correct 13 ms 256 KB Output is correct
58 Correct 8 ms 380 KB Output is correct
59 Correct 7 ms 256 KB Output is correct
60 Correct 7 ms 256 KB Output is correct
61 Correct 8 ms 256 KB Output is correct
62 Correct 1 ms 256 KB Output is correct
63 Correct 0 ms 256 KB Output is correct
64 Correct 0 ms 256 KB Output is correct
65 Correct 1 ms 256 KB Output is correct
66 Correct 0 ms 256 KB Output is correct
67 Correct 1 ms 256 KB Output is correct
68 Correct 0 ms 256 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 0 ms 256 KB Output is correct
73 Correct 1 ms 256 KB Output is correct
74 Correct 1 ms 256 KB Output is correct
75 Correct 1 ms 384 KB Output is correct
76 Correct 0 ms 256 KB Output is correct
77 Correct 0 ms 256 KB Output is correct
78 Correct 0 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 0 ms 256 KB Output is correct
86 Correct 0 ms 256 KB Output is correct
87 Correct 0 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 256 KB Output is correct