oj.uz

Submission #884625

# Submission time Handle Problem Language Result Execution time Memory
884625 2023-12-07T18:46:19 Z jamjanek Counting Mushrooms (IOI20_mushrooms) C++14
100 / 100
 5 ms 728 KB 
#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
void wypiszvector(vector<int>&vec){
	printf("{");
	for(auto j: vec)printf("%d,", j);
	printf("}\n");
}
 
const int stala = 6;
int maska[83] = {0,0,0,4,8,59,9,43,41,0,0,63,1,0,32,2,16,0,33,47,35,0,12,18,34,0,45,13,51,50,0,0,24,40,26,27,58,0,36,5,37,55,39,0,10,42,11,57,25,0,20,6,22,38,54,0,0,46,17,44,19,0,3,62,61,0,49,48,14,0,31,29,30,28,15,0,56,7,52,23,53,21,60,};
vector<int>zapytanie[83] = {{4,1,6,2,5,0,3,},{},{2,4,5,6,0,1,3,},{},{},{},{},{},{},{1,2,3,5,4,6,0,},{3,6,4,1,2,},{},{},{2,5,1,3,0,4,},{},{},{},{4,6,5,3,2,0,1,},{},{},{},{3,5,2,0,1,6,},{},{},{},{3,5,0,1,4,6,},{},{},{},{},{0,3,1,2,5,4,},{1,6,0,2,3,5,},{},{},{},{},{},{5,1,4,2,0,6,},{},{},{},{},{},{4,3,5,0,1,6,},{},{},{},{},{},{1,6,4,2,0,5,},{},{},{},{},{},{5,1,0,3,6,4,},{0,5,6,1,3,2,4,},{},{},{},{},{2,5,6,0,3,},{},{},{},{1,6,4,2,0,3,},{},{},{},{4,1,5,6,0,3,2,},{},{},{},{},{},{6,5,4,3,2,1,0,},{},{},{},{},{},{},{},};
vector<int>graf[83] = {{1,2,9,30,55,75,82,},{},{-1,3,4,5,6,7,8,},{},{},{},{},{},{},{-1,10,13,17,21,25,29,},{11,-1,12,},{},{},{14,15,16,},{},{},{},{-1,-1,-1,18,19,20,},{},{},{},{-1,22,23,24,},{},{},{},{-1,-1,26,27,-1,28,},{},{},{},{},{-1,31,37,43,49,},{-1,32,33,34,35,36,},{},{},{},{},{},{-1,38,39,40,41,42,},{},{},{},{},{},{-1,44,45,46,47,48,},{},{},{},{},{},{-1,50,51,52,53,54,},{},{},{},{},{},{-1,56,61,65,69,74,},{-1,-1,-1,57,58,59,60,},{},{},{},{},{-1,62,63,64,},{},{},{},{-1,66,67,68,},{},{},{},{-1,-1,70,71,72,73,},{},{},{},{},{},{-1,76,77,78,79,80,81,},{},{},{},{},{},{},{},};
 
const int stala2 = 7;
int maska2[157] = {0,0,0,0,64,16,80,17,81,0,96,32,112,48,113,49,0,1,65,23,87,19,83,0,97,33,119,55,115,51,0,3,67,7,71,0,39,103,35,99,0,0,31,95,15,79,11,75,0,127,63,111,47,107,43,0,72,8,73,9,91,27,0,59,123,40,104,41,105,0,24,88,25,89,0,120,56,121,57,0,0,5,69,21,85,0,53,117,37,101,0,2,66,4,68,20,84,0,98,34,100,36,116,52,0,6,70,22,86,18,82,0,114,50,118,54,102,38,0,0,125,124,109,108,77,76,0,12,13,44,45,60,61,0,126,110,92,78,93,74,0,28,10,29,14,62,46,0,94,122,90,106,0,30,58,26,42,};
vector<int>zapytanie2[157] = {{-1,1,2,3,0,4,},{-1,5,1,0,2,3,4,6,},{-1,0,1,2,3,4,5,6,7,},{},{},{},{},{},{},{-1,0,1,2,3,5,4,6,7,},{},{},{},{},{},{},{-1,0,1,3,2,4,5,6,7,},{},{},{},{},{},{},{-1,0,2,3,5,4,1,6,7,},{},{},{},{},{},{},{-1,0,1,2,4,3,5,6,7,},{},{},{},{},{-1,0,1,2,3,6,4,5,7,},{},{},{},{},{-1,1,2,4,3,5,0,6,},{-1,0,1,3,2,5,4,6,7,},{},{},{},{},{},{},{-1,0,1,2,3,4,5,6,7,},{},{},{},{},{},{},{-1,0,1,2,3,5,6,4,7,},{},{},{},{},{},{},{-1,0,1,2,4,5,6,3,7,},{},{},{},{},{},{},{-1,0,1,2,3,4,5,6,7,},{},{},{},{},{-1,0,1,2,3,4,5,6,7,},{},{},{},{},{-1,1,3,5,0,2,4,6,},{-1,0,1,2,3,4,5,6,7,},{},{},{},{},{-1,0,1,2,3,5,6,4,7,},{},{},{},{},{-1,0,1,3,4,5,6,7,},{},{},{},{},{},{},{-1,0,1,3,4,5,2,6,7,},{},{},{},{},{},{},{-1,3,2,0,1,4,5,6,7,},{},{},{},{},{},{},{-1,0,1,3,4,2,5,6,7,},{},{},{},{},{},{},{-1,1,2,0,5,6,3,4,7,},{-1,0,2,3,5,4,6,7,1,},{},{},{},{},{},{},{-1,0,5,2,6,7,1,},{},{},{},{},{},{},{-1,0,1,2,3,4,6,7,5,},{},{},{},{},{},{},{-1,0,2,1,6,7,3,5,},{},{},{},{},{},{},{-1,0,1,2,3,4,5,6,},{},{},{},{},{-1,0,1,2,3,4,5,6,},{},{},{},{},};
vector<int>graf2[157] = {{-1,1,40,79,118,},{-1,2,9,16,23,30,35,},{-1,3,4,5,6,7,8,},{},{},{},{},{},{},{-1,-1,10,11,12,13,14,15,},{},{},{},{},{},{},{-1,-1,-1,17,18,19,20,21,22,},{},{},{},{},{},{},{-1,-1,24,25,26,27,28,29,},{},{},{},{},{},{},{-1,-1,-1,31,32,33,34,},{},{},{},{},{-1,-1,-1,36,37,38,39,},{},{},{},{},{-1,41,48,55,62,69,74,},{-1,-1,-1,42,43,44,45,46,47,},{},{},{},{},{},{},{-1,-1,49,50,51,52,53,54,},{},{},{},{},{},{},{-1,-1,56,57,58,59,60,61,},{},{},{},{},{},{},{-1,-1,-1,63,64,65,66,67,68,},{},{},{},{},{},{},{-1,-1,-1,70,71,72,73,},{},{},{},{},{-1,-1,75,76,77,78,},{},{},{},{},{-1,80,85,90,97,104,111,},{-1,-1,-1,-1,-1,81,82,83,84,},{},{},{},{},{-1,-1,-1,-1,-1,86,87,88,89,},{},{},{},{},{-1,91,92,93,94,95,96,},{},{},{},{},{},{},{-1,-1,98,99,100,101,102,103,},{},{},{},{},{},{},{-1,105,106,107,108,109,110,},{},{},{},{},{},{},{-1,-1,112,113,114,115,116,117,},{},{},{},{},{},{},{-1,-1,119,126,133,140,147,152,},{-1,-1,120,121,122,123,124,125,},{},{},{},{},{},{},{-1,127,128,129,130,131,132,},{},{},{},{},{},{},{-1,-1,134,135,136,137,138,139,},{},{},{},{},{},{},{-1,-1,141,142,143,144,145,146,},{},{},{},{},{},{},{-1,-1,-1,148,149,150,151,},{},{},{},{},{-1,-1,-1,153,154,155,156,},{},{},{},{},};


const int stala3 = 5;
int maska3[39] = {0,1,0,17,29,25,0,0,3,9,5,13,0,27,19,31,16,24,21,28,0,12,4,8,2,15,7,11,0,23,20,30,18,26,0,14,6,10,22,};
vector<int>zapytanie3[39] = {{-3,1,-1,-2,2,0,3,4,5,},{},{-3,-2,-1,0,1,2,4,3,},{},{},{},{-3,-2,-1,0,1,2,3,5,4,},{},{},{},{},{},{-3,-2,3,0,-1,2,5,1,4,},{},{},{},{},{},{},{},{-3,-2,1,0,2,5,-1,3,4,},{},{},{},{},{},{},{},{-3,-2,-1,1,2,3,5,0,4,},{},{},{},{},{},{-3,-2,-1,0,1,2,3,4,},{},{},{},{},};
vector<int>graf3[39] = {{-1,1,2,6,12,20,28,34,38,},{},{-1,-1,-1,-1,-1,3,4,5,},{},{},{},{-1,-1,-1,7,-1,8,9,10,11,},{},{},{},{},{},{-1,-1,13,14,15,16,17,18,19,},{},{},{},{},{},{},{},{-1,-1,21,22,23,24,25,26,27,},{},{},{},{},{},{},{},{-1,-1,-1,29,-1,30,31,32,33,},{},{},{},{},{},{-1,-1,-1,-1,35,36,37,},{},{},{},{},};



vector<int>A[2];
int Ac[2];
int it;
int count_mushrooms1(int n){
	while(it<n){
//		printf("it = %d\n", it);
		vector<int>pom;
		bool czy = 0;
		if(A[1].size()>A[0].size())czy = 1;
		int pom1 = 0;
		while(it<n && pom.size()<2*A[czy].size()){
			pom.push_back(A[czy][pom1++]);
			pom.push_back(it);
			it++;
		}
		int ans = use_machine(pom);
//		printf("vec: = ");for(auto j: pom)printf("%d ", j);printf("\n");
//		printf("ans = %d\n", ans);
		if(ans%2==0)
			A[czy].push_back(it-1);
		else
			A[!czy].push_back(it-1);
		Ac[!czy]+=(ans+1)/2;
		Ac[czy]+=pom1-(ans+1)/2;
		if(pom1==2){
			if(ans<2)
				A[czy].push_back(it-2);
			else
				A[!czy].push_back(it-2);
		}
	}
//	printf("res = %d\n", Ac[0]);
	return Ac[0];
}
int count_mushrooms(int n){
	A[0].push_back(0);
	it = 1;
	Ac[0] = 1;
	Ac[1] = 0;
	int akt = 0;
	for(int ile=0;ile<40;ile++)
	{
		if(Ac[0]>=2 && Ac[1]>=2){
			if(n<=stala3+it)
				return count_mushrooms1(n);
			int x = 0;
			while(graf3[x].size()>0){
				vector<int>pom;
				pom = zapytanie3[x];
				for(auto &j: pom)
					if(j>0)
						j+=akt;
					else{
						//-3, -2, -1, 0 -> 
						j = A[(-j)%2][(-j)/2];
					}
				int c = use_machine(pom);
		//		wypiszvector(zapytanie[x]);
				x = graf3[x][c];
			}
			x = maska3[x];
			for(int i=0;i<stala3;i++){
				A[(x>>i)&1].push_back(akt+i+1);
				Ac[(x>>i)&1]++;
			}
			it+=stala3;
			akt+=stala3;
			continue;
		}
		if(Ac[1]==0){
			if(n<=stala+it)
				return count_mushrooms1(n);
			int x = 0;
			while(graf[x].size()>0){
				vector<int>pom;
				pom = zapytanie[x];
				for(auto &j: pom)
					if(j>0)
						j+=akt;
				int c = use_machine(pom);
		//		wypiszvector(zapytanie[x]);
				x = graf[x][c];
			}
			x = maska[x];
			for(int i=0;i<stala;i++){
				A[(x>>i)&1].push_back(akt+i+1);
				Ac[(x>>i)&1]++;
			}
			it+=stala;
			akt+=stala;
		}
		else{
			if(n<=stala2+it)
				return count_mushrooms1(n);
			int x = 0;
			while(graf2[x].size()>0){
				vector<int>pom;
				pom = zapytanie2[x];
				for(auto &j: pom){
					if(j>0)
						j+=akt;
					else if(j<0)
						j = A[1][0];
				}
				int c = use_machine(pom);
		//		wypiszvector(zapytanie[x]);
				x = graf2[x][c];
			}
			x = maska2[x];
			for(int i=0;i<stala2;i++){
				A[(x>>i)&1].push_back(akt+i+1);
				Ac[(x>>i)&1]++;
			}
			it+=stala2;
			akt+=stala2;
		}
	}
	return count_mushrooms1(n);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 3 ms 464 KB Output is correct
8 Correct 4 ms 464 KB Output is correct
9 Correct 4 ms 472 KB Output is correct
10 Correct 4 ms 452 KB Output is correct
11 Correct 4 ms 472 KB Output is correct
12 Correct 4 ms 456 KB Output is correct
13 Correct 4 ms 460 KB Output is correct
14 Correct 2 ms 472 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 4 ms 476 KB Output is correct
17 Correct 2 ms 452 KB Output is correct
18 Correct 3 ms 460 KB Output is correct
19 Correct 4 ms 472 KB Output is correct
20 Correct 4 ms 456 KB Output is correct
21 Correct 4 ms 460 KB Output is correct
22 Correct 4 ms 468 KB Output is correct
23 Correct 4 ms 460 KB Output is correct
24 Correct 2 ms 472 KB Output is correct
25 Correct 4 ms 476 KB Output is correct
26 Correct 4 ms 472 KB Output is correct
27 Correct 5 ms 452 KB Output is correct
28 Correct 4 ms 468 KB Output is correct
29 Correct 4 ms 472 KB Output is correct
30 Correct 4 ms 472 KB Output is correct
31 Correct 4 ms 668 KB Output is correct
32 Correct 4 ms 472 KB Output is correct
33 Correct 4 ms 468 KB Output is correct
34 Correct 4 ms 468 KB Output is correct
35 Correct 4 ms 480 KB Output is correct
36 Correct 4 ms 472 KB Output is correct
37 Correct 4 ms 724 KB Output is correct
38 Correct 4 ms 472 KB Output is correct
39 Correct 4 ms 476 KB Output is correct
40 Correct 4 ms 476 KB Output is correct
41 Correct 4 ms 480 KB Output is correct
42 Correct 4 ms 476 KB Output is correct
43 Correct 5 ms 724 KB Output is correct
44 Correct 4 ms 728 KB Output is correct
45 Correct 4 ms 468 KB Output is correct
46 Correct 4 ms 480 KB Output is correct
47 Correct 4 ms 476 KB Output is correct
48 Correct 4 ms 476 KB Output is correct
49 Correct 4 ms 476 KB Output is correct
50 Correct 4 ms 468 KB Output is correct
51 Correct 4 ms 476 KB Output is correct
52 Correct 4 ms 472 KB Output is correct
53 Correct 4 ms 476 KB Output is correct
54 Correct 4 ms 472 KB Output is correct
55 Correct 4 ms 476 KB Output is correct
56 Correct 5 ms 620 KB Output is correct
57 Correct 5 ms 708 KB Output is correct
58 Correct 4 ms 476 KB Output is correct
59 Correct 4 ms 728 KB Output is correct
60 Correct 4 ms 476 KB Output is correct
61 Correct 4 ms 476 KB Output is correct
62 Correct 0 ms 344 KB Output is correct
63 Correct 0 ms 344 KB Output is correct
64 Correct 0 ms 344 KB Output is correct
65 Correct 1 ms 420 KB Output is correct
66 Correct 0 ms 344 KB Output is correct
67 Correct 0 ms 344 KB Output is correct
68 Correct 0 ms 344 KB Output is correct
69 Correct 0 ms 344 KB Output is correct
70 Correct 0 ms 344 KB Output is correct
71 Correct 0 ms 344 KB Output is correct
72 Correct 1 ms 344 KB Output is correct
73 Correct 0 ms 344 KB Output is correct
74 Correct 0 ms 344 KB Output is correct
75 Correct 0 ms 344 KB Output is correct
76 Correct 0 ms 344 KB Output is correct
77 Correct 0 ms 344 KB Output is correct
78 Correct 0 ms 344 KB Output is correct
79 Correct 1 ms 344 KB Output is correct
80 Correct 0 ms 344 KB Output is correct
81 Correct 0 ms 344 KB Output is correct
82 Correct 0 ms 344 KB Output is correct
83 Correct 0 ms 344 KB Output is correct
84 Correct 0 ms 344 KB Output is correct
85 Correct 0 ms 344 KB Output is correct
86 Correct 0 ms 344 KB Output is correct
87 Correct 0 ms 344 KB Output is correct
88 Correct 0 ms 344 KB Output is correct
89 Correct 0 ms 344 KB Output is correct
90 Correct 0 ms 344 KB Output is correct
91 Correct 0 ms 344 KB Output is correct