oj.uz

답안 #308533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
308533 2020-10-01T13:29:21 Z CaroLinda 버섯 세기 (IOI20_mushrooms) C++14
100 / 100
 10 ms 512 KB 
#include "mushrooms.h"
#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define debug //printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()

const int CTE = 103 ;

using namespace std ;

int count_mushrooms(int n) 
{

	vector<int> type(n,1) ;
	vector<int> known[2] ;
	int res ;

	if( n <= 226 )
	{

		for(int i = 1 ; i < n ; i++ )
		{
			type[i] = type[i-1] ;
			if(use_machine( {i,i-1} )) type[i] ^= 1 ;
		}

		int cnt = 0 ;
		lp(i,0,n) cnt += type[i] ;
		return cnt ;
	}

	//Finding out about 5
	if(use_machine( {0,1} )) type[1] = 0 ;
	if( use_machine({0,2}) ) type[2] = 0 ;
	lp(i,0,3) known[type[i]].push_back(i); 

	lp(i,0,2)
	{
		if(sz(known[i]) < 2) continue ;

		res = use_machine( {known[i][0] , 3 , known[i][1] ,4} ) ;
		
		if( res&1 ) type[4] = !i , res-- ;
		else type[4] = i ;

		if(res == 0) type[3] = i ;
		else type[3] = !i ;

	}

	lp(i,3,5) known[ type[i] ].push_back(i) ;

	int undiscovered =  5;

	while( max( sz(known[0])  , sz(known[1]) ) < CTE )
	{
		//debug("Printando os tamanhos: %d %d\n" , sz(known[0]) , sz(known[1])) ;

		int idx = ( sz(known[0]) > sz(known[1]) ) ? 0 : 1 ;
		
		vector<int> q ;
		
		q.pb( known[idx][0] ) ;
		q.pb(undiscovered); 
		q.pb( known[idx][1] ) ;
		q.pb(undiscovered+1); 
		q.pb( known[idx][2] ) ;
		q.pb(undiscovered+2); 

		res = use_machine(q) ;

		if(res&1) type[undiscovered+2] = !idx , res-- ;
		else type[undiscovered+2] = idx ;

		known[ type[undiscovered+2] ].pb(undiscovered+2) ;

		if(res == 0 || res == 4) 
		{
			type[undiscovered] = type[undiscovered+1] = (res == 0) ? idx : !idx ;
			
			lp(i,0,2) known[ type[undiscovered+i] ].pb(undiscovered+i) ;

			undiscovered += 3 ;

			continue ;
		}

		if( min(sz(known[0]) , sz(known[1])) < 2 )
		{
			res = use_machine({ undiscovered, known[idx][0] }) ;
			
			if(res == 0 ) type[undiscovered] = idx ;
			else type[undiscovered] = !idx ;

			type[undiscovered+1] = !type[undiscovered ];

			lp(i,0,2) known[ type[undiscovered+i] ].pb(undiscovered+i) ;

			undiscovered += 3 ;
			continue ;
		}

		q.clear() ;
		q.push_back(known[!idx][0]) ;
		q.push_back(undiscovered) ;
		q.push_back(known[!idx][1]) ;
		q.push_back(known[idx][0]) ;
		q.push_back(undiscovered+1); 
		q.push_back(known[idx][1] ) ;
		q.push_back(undiscovered+3); 
		q.push_back(known[idx][2] ) ;
		q.push_back(undiscovered+4); 

		res = use_machine(q) - 1;

		if(res&1 ) type[undiscovered+4] = !idx , res-- ;
		else type[undiscovered+4] = idx ;

		if(res <= 2)
		{
			type[ undiscovered ] = !idx ;
			type[ undiscovered+1 ] = idx ;
			type[undiscovered+3] = (res == 2) ? !idx : idx ;
		}
		else
		{
			type[undiscovered] = idx ;
			type[undiscovered+1] = !idx ;
			type[undiscovered+3] = ( res == 4 ) ? idx : !idx ;
		}

		lp(i,0,5)
			if(i != 2 ) known[ type[undiscovered+i] ].push_back(undiscovered+i) ;

		undiscovered += 5 ;

	}


	int ans = 0 ;

	//lp(i,0,undiscovered) cout << !type[i] << " " ;
	//cout << endl ;

	while( n - undiscovered )
	{

		int idx = 0 ;
		if( sz(known[1]) > sz(known[0]) ) idx = 1 ;

		int qtd = min( n-undiscovered, sz(known[idx]) ) ;

		vector<int> q ;
		lp(i,0,qtd )
			q.pb( known[idx][i] ) , q.pb(undiscovered + i) ;

		res = use_machine(q) ;

		int last = undiscovered+qtd-1 ;

		if(res&1) type[last] = !idx , res-- ;
		else type[last] = idx ;

		known[type[last]].pb(last); 

		res /= 2 ;
		
		if(idx == 1) ans += qtd-1-res ;
		else ans += res ;

		undiscovered += qtd ;

	}

	ans += sz(known[1]) ;

	return ans ;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 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 Correct 2 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 9 ms 384 KB Output is correct
12 Correct 9 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 Correct 7 ms 384 KB Output is correct
16 Correct 7 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 7 ms 384 KB Output is correct
19 Correct 7 ms 384 KB Output is correct
20 Correct 7 ms 384 KB Output is correct
21 Correct 7 ms 384 KB Output is correct
22 Correct 7 ms 384 KB Output is correct
23 Correct 7 ms 384 KB Output is correct
24 Correct 4 ms 420 KB Output is correct
25 Correct 7 ms 384 KB Output is correct
26 Correct 7 ms 384 KB Output is correct
27 Correct 7 ms 384 KB Output is correct
28 Correct 7 ms 384 KB Output is correct
29 Correct 7 ms 460 KB Output is correct
30 Correct 9 ms 384 KB Output is correct
31 Correct 9 ms 384 KB Output is correct
32 Correct 9 ms 384 KB Output is correct
33 Correct 10 ms 384 KB Output is correct
34 Correct 7 ms 384 KB Output is correct
35 Correct 7 ms 384 KB Output is correct
36 Correct 9 ms 512 KB Output is correct
37 Correct 7 ms 384 KB Output is correct
38 Correct 7 ms 384 KB Output is correct
39 Correct 7 ms 384 KB Output is correct
40 Correct 7 ms 384 KB Output is correct
41 Correct 7 ms 384 KB Output is correct
42 Correct 8 ms 384 KB Output is correct
43 Correct 7 ms 384 KB Output is correct
44 Correct 7 ms 384 KB Output is correct
45 Correct 7 ms 384 KB Output is correct
46 Correct 9 ms 384 KB Output is correct
47 Correct 6 ms 460 KB Output is correct
48 Correct 7 ms 384 KB Output is correct
49 Correct 8 ms 384 KB Output is correct
50 Correct 8 ms 384 KB Output is correct
51 Correct 9 ms 384 KB Output is correct
52 Correct 9 ms 384 KB Output is correct
53 Correct 7 ms 384 KB Output is correct
54 Correct 7 ms 384 KB Output is correct
55 Correct 7 ms 384 KB Output is correct
56 Correct 8 ms 384 KB Output is correct
57 Correct 7 ms 384 KB Output is correct
58 Correct 9 ms 384 KB Output is correct
59 Correct 8 ms 384 KB Output is correct
60 Correct 7 ms 384 KB Output is correct
61 Correct 8 ms 384 KB Output is correct
62 Correct 1 ms 256 KB Output is correct
63 Correct 1 ms 256 KB Output is correct
64 Correct 0 ms 256 KB Output is correct
65 Correct 0 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 0 ms 256 KB Output is correct
69 Correct 0 ms 256 KB Output is correct
70 Correct 1 ms 256 KB Output is correct
71 Correct 0 ms 256 KB Output is correct
72 Correct 0 ms 256 KB Output is correct
73 Correct 0 ms 256 KB Output is correct
74 Correct 0 ms 256 KB Output is correct
75 Correct 0 ms 256 KB Output is correct
76 Correct 0 ms 256 KB Output is correct
77 Correct 1 ms 256 KB Output is correct
78 Correct 0 ms 256 KB Output is correct
79 Correct 0 ms 256 KB Output is correct
80 Correct 0 ms 256 KB Output is correct
81 Correct 0 ms 256 KB Output is correct
82 Correct 1 ms 256 KB Output is correct
83 Correct 0 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 1 ms 256 KB Output is correct
87 Correct 0 ms 256 KB Output is correct
88 Correct 0 ms 256 KB Output is correct
89 Correct 1 ms 256 KB Output is correct
90 Correct 0 ms 256 KB Output is correct
91 Correct 1 ms 256 KB Output is correct