oj.uz

Submission #303813

# Submission time Handle Problem Language Result Execution time Memory
303813 2020-09-20T16:23:47 Z errorgorn Counting Mushrooms (IOI20_mushrooms) C++17
92.623 / 100
 10 ms 384 KB 
#include "mushrooms.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

const int LIM=80; //play with this

int n;
vector<int> red;
vector<int> blue;

int count_mushrooms(int N) {
	n=N;
	
	if (n<300){
		int ans=1;
		
		for (int x=1;x<n;x+=2){
			if (x==n-1) ans+=1-use_machine({0,x});
			else ans+=2-use_machine({x,0,x+1});
		}
		
		return ans;
	}
	
	red.push_back(0);
	
	int idx=1;
	while (sz(red)<2 && sz(blue)<2){
		if (use_machine({0,idx})==0) red.push_back(idx++);
		else blue.push_back(idx++);
	}
	
	rep(zzz,0,LIM){
		if (sz(red)>=2){
			int temp=use_machine({idx,red[0],idx+1,red[1]});
			
			if (temp&1) blue.push_back(idx);
			else red.push_back(idx);
			
			if (temp&2) blue.push_back(idx+1);
			else red.push_back(idx+1);
		}
		else{
			int temp=use_machine({idx,blue[0],idx+1,blue[1]});
			
			if (temp&1) red.push_back(idx);
			else blue.push_back(idx);
			
			if (temp&2) red.push_back(idx+1);
			else blue.push_back(idx+1);
		}
		idx+=2;
	}
	
	int ans=sz(red);
	//cout<<sz(red)<<" "<<sz(blue)<<endl;
	
	while (idx<n){ //it is possible to save some queries here by using the last character but do it later (okay done)
		vector<int> temp;
		
		if (sz(red)>sz(blue)){
			rep(x,0,sz(red)){
				temp.push_back(red[x]);
				if (idx+x<n) temp.push_back(idx+x);
			}
			
			int val=use_machine(temp);
			
			ans+=sz(temp)-sz(red)-(val+1)/2;
			idx+=sz(red);
			
			if (val&1) blue.push_back(idx-1);
			else red.push_back(idx-1);
		}
		else{
			rep(x,0,sz(blue)){
				temp.push_back(blue[x]);
				if (idx+x<n) temp.push_back(idx+x);
			}
			
			int val=use_machine(temp);
			
			ans+=(val+1)/2;
			idx+=sz(blue);
			
			if (val&1) red.push_back(idx-1);
			else blue.push_back(idx-1);
		}
	}
	
	return ans;
}

Subtask #1
92.623 / 100.0

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