oj.uz

Submission #884593

# Submission time Handle Problem Language Result Execution time Memory
884593 2023-12-07T17:58:50 Z jamjanek Counting Mushrooms (IOI20_mushrooms) C++14
81.8841 / 100
 6 ms 760 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 = 8;
int maska[362] = {0,0,0,16,1,24,65,26,190,30,62,0,0,64,2,0,0,8,255,0,4,32,128,0,6,191,10,31,0,36,17,160,127,95,0,27,81,14,63,38,0,164,91,25,0,166,89,174,46,0,0,193,129,60,0,33,0,20,28,0,18,161,0,225,22,0,0,3,5,0,56,58,0,9,254,0,48,188,126,0,54,52,0,239,144,0,80,175,0,47,97,229,0,37,158,0,165,94,0,69,0,7,15,0,11,186,0,73,67,0,176,184,0,180,182,0,0,231,167,0,111,39,0,88,101,0,90,152,154,0,75,71,79,103,0,0,96,12,0,132,66,40,172,44,238,110,0,0,74,72,0,223,78,0,247,136,0,34,159,0,102,100,0,142,224,0,228,230,0,0,68,130,70,0,134,192,253,0,251,189,145,0,42,19,0,168,83,123,0,0,183,181,0,219,153,155,0,177,245,162,0,138,29,0,119,49,241,113,0,0,61,57,0,125,121,0,59,185,0,21,249,0,187,87,23,0,170,209,0,117,93,53,217,55,85,0,0,250,122,0,133,148,120,0,248,252,112,0,244,240,0,0,50,178,0,207,246,0,143,146,0,222,107,0,150,135,218,0,0,197,77,0,237,109,0,13,105,0,208,116,156,0,124,216,0,139,0,131,199,203,0,43,235,0,35,118,82,99,0,84,0,137,201,92,0,41,233,0,173,45,0,86,195,171,227,163,169,0,76,0,215,243,211,179,147,0,140,236,221,108,0,51,115,196,151,213,0,200,104,232,157,206,0,149,198,98,194,226,0,202,234,106,0,214,212,210,220,242,205,114,141,204,};
vector<int>zapytanie[362] = {{5,4,2,3,6,8,0,7,1,},{},{5,1,4,0,2,8,3,7,6,},{},{},{},{},{},{},{},{},{7,6,0,4,8,5,3,1,2,},{7,4,3,2,6,5,0,1,},{},{},{6,1,5,8,2,7,3,},{4,6,1,5,3,0,2,},{},{},{3,8,1,4,7,5,2,6,0,},{},{},{},{6,5,4,0,1,8,2,7,},{},{},{},{},{6,3,7,0,1,8,2,},{},{},{},{},{},{1,4,2,0,6,7,3,8,},{},{},{},{},{},{7,1,0,5,4,2,8,3,6,},{},{},{},{0,4,5,7,1,2,8,3,},{},{},{},{},{6,4,3,5,2,0,7,8,1,},{2,6,0,5,3,4,8,7,},{},{},{},{7,0,2,1,6,5,4,8,3,},{},{4,7,8,2,3,5,6,0,1,},{},{},{5,4,8,0,1,7,3,},{},{},{5,0,4,3,7,2,1,},{},{},{1,3,0,6,4,5,8,7,},{5,1,2,8,6,7,4,3,},{},{},{3,7,4,1,0,2,8,6,5,},{},{},{5,0,3,8,1,6,4,},{},{},{5,6,1,7,0,8,2,},{},{},{},{3,2,5,8,4,1,7,},{},{},{5,0,3,7,1,2,6,4,8,},{},{},{5,2,1,7,4,3,6,0,8,},{},{},{8,0,7,4,5,6,1,3,2,},{},{},{},{5,6,2,8,4,0,3,1,7,},{},{},{5,2,4,7,0,8,6,1,3,},{},{},{7,8,0,6,4,2,5,1,3,},{},{4,0,3,6,5,8,2,1,},{},{},{5,6,8,0,2,3,4,1,},{},{},{5,1,4,3,6,2,8,7,},{},{},{3,4,0,7,8,5,2,1,6,},{},{},{3,6,1,8,7,2,0,},{},{},{8,1,3,5,0,4,6,2,},{5,3,7,8,0,6,4,2,},{},{},{4,1,3,0,5,8,2,7,6,},{},{},{5,6,8,1,3,4,7,2,0,},{},{},{7,8,0,5,2,1,6,},{},{},{},{6,1,7,0,3,5,4,},{},{},{},{},{6,7,2,1,0,5,8,3,4,},{7,6,4,3,2,0,5,1,},{},{},{8,3,5,7,1,4,0,6,},{},{},{},{},{},{},{},{3,5,6,0,8,1,2,7,4,},{5,0,8,6,7,2,4,1,3,},{},{},{5,6,4,8,7,1,2,0,},{},{},{5,4,6,3,8,2,7,},{},{},{5,6,2,0,4,8,3,},{},{},{3,2,6,4,1,7,5,8,0,},{},{},{5,6,3,8,1,7,2,0,4,},{},{},{3,6,1,8,0,2,4,7,},{},{},{7,3,1,4,0,6,5,8,2,},{7,6,8,1,2,5,4,0,},{},{},{},{3,2,6,0,1,7,5,8,},{},{},{},{7,1,3,4,2,8,6,5,0,},{},{},{},{5,6,1,3,2,4,0,7,},{},{},{4,3,5,1,2,0,7,6,8,},{},{},{},{6,3,5,8,1,4,7,0,},{4,7,8,6,3,2,5,1,0,},{},{},{2,7,8,3,1,6,4,5,0,},{},{},{},{7,2,0,3,8,4,6,1,},{},{},{},{5,6,7,0,3,8,2,4,1,},{},{},{6,3,5,0,4,1,2,7,8,},{},{},{},{},{7,2,0,8,3,5,4,1,6,},{3,6,4,7,2,0,1,8,5,},{},{},{3,6,8,4,5,1,2,0,7,},{},{},{5,6,0,8,3,2,4,},{},{},{5,6,0,1,7,2,4,3,},{},{},{5,6,1,2,3,8,0,7,4,},{},{},{},{5,6,2,8,4,7,0,},{},{},{6,1,4,2,8,0,3,7,5,},{},{},{},{},{},{},{0,1,3,8,5,6,7,4,2,},{7,1,2,5,0,3,4,8,6,},{},{},{8,1,7,4,6,0,5,2,},{},{},{},{3,2,7,0,5,8,4,6,},{},{},{},{3,6,4,7,2,8,},{},{},{7,3,4,1,5,6,8,0,2,},{5,4,1,3,8,7,2,6,0,},{},{},{5,6,1,3,2,7,8,0,},{},{},{5,6,0,1,8,7,2,3,},{},{},{5,6,2,8,4,3,1,},{},{},{5,3,4,2,8,1,6,7,},{},{},{},{6,0,5,2,4,1,7,3,},{5,3,6,7,8,},{},{},{5,3,8,4,7,1,2,},{},{},{5,7,2,6,8,0,1,3,4,},{},{},{4,7,5,8,2,6,1,0,},{},{},{},{5,7,3,2,8,1,4,0,6,},{},{},{6,5,0,7,3,1,8,2,4,},{},{7,5,8,0,4,1,6,3,},{},{},{},{7,3,1,2,6,8,5,4,},{},{},{5,0,3,8,2,4,1,6,},{},{},{},{},{3,7,1,5,8,4,0,6,2,},{},{7,2,0,4,5,6,8,3,},{},{},{},{4,1,6,5,3,0,2,7,},{},{},{3,5,0,6,8,4,7,2,},{},{},{7,8,4,6,5,3,2,0,1,},{},{},{},{},{},{},{0,6,8,1,2,5,7,3,4,},{},{6,1,5,7,2,3,8,0,},{},{},{},{},{},{6,7,5,3,8,4,2,1,0,},{},{},{},{},{6,5,2,3,0,8,7,},{},{},{},{},{},{8,5,0,3,6,2,1,4,7,},{},{},{},{},{},{6,5,8,3,7,0,2,4,1,},{},{},{},{},{},{6,0,3,7,8,2,5,},{},{},{},{2,3,7,8,5,1,6,4,0,},{},{},{},{},{},{},{},{},{},};
vector<int>graf[362] = {{1,2,11,49,134,235,317,352,361,},{},{-1,3,4,5,6,7,8,9,10,},{},{},{},{},{},{},{},{},{-1,12,15,23,28,34,40,44,},{-1,13,14,},{},{},{16,19,22,},{-1,17,18,},{},{},{-1,20,21,},{},{},{},{-1,-1,24,25,26,-1,27,},{},{},{},{},{-1,29,30,31,32,33,},{},{},{},{},{},{-1,35,-1,36,37,38,39,},{},{},{},{},{},{-1,41,-1,42,43,},{},{},{},{-1,45,46,47,-1,48,},{},{},{},{},{-1,50,54,65,82,98,115,129,133,},{-1,51,52,-1,53,},{},{},{},{-1,-1,55,56,59,62,},{},{-1,-1,57,58,},{},{},{-1,60,-1,-1,61,},{},{},{-1,-1,-1,63,-1,64,},{},{},{-1,66,69,72,75,78,79,},{-1,-1,67,68,},{},{},{-1,-1,-1,70,-1,71,},{},{},{-1,-1,-1,73,74,},{},{},{-1,76,-1,77,},{},{},{},{-1,80,-1,81,},{},{},{-1,83,84,85,88,91,92,95,},{},{},{-1,-1,-1,86,-1,87,},{},{},{-1,-1,-1,89,90,},{},{},{},{-1,-1,-1,-1,93,94,},{},{},{-1,96,97,},{},{},{-1,-1,99,100,103,106,109,112,},{},{-1,-1,-1,101,102,},{},{},{-1,-1,-1,104,-1,105,},{},{},{-1,-1,-1,107,-1,108,},{},{},{-1,-1,-1,110,-1,111,},{},{},{-1,-1,-1,113,-1,114,},{},{},{-1,-1,116,119,122,125,128,},{-1,-1,-1,-1,-1,117,-1,118,},{},{},{-1,-1,120,-1,-1,121,},{},{},{-1,-1,-1,123,-1,-1,124,},{},{},{-1,-1,-1,126,127,},{},{},{},{-1,-1,-1,130,131,132,},{},{},{},{},{-1,135,138,146,168,188,208,228,234,},{-1,136,137,},{},{},{-1,139,140,141,142,143,144,145,},{},{},{},{},{},{},{},{-1,147,150,153,156,159,162,165,},{-1,-1,148,-1,149,},{},{},{-1,-1,-1,151,-1,-1,152,},{},{},{-1,-1,154,-1,155,},{},{},{-1,-1,157,-1,158,},{},{},{-1,-1,-1,160,-1,161,},{},{},{-1,-1,-1,-1,-1,163,164,},{},{},{-1,-1,-1,-1,166,-1,167,},{},{},{-1,169,172,173,177,181,184,},{-1,170,-1,-1,171,},{},{},{},{-1,-1,174,175,176,},{},{},{},{-1,-1,-1,178,179,-1,180,},{},{},{},{-1,-1,-1,-1,182,183,},{},{},{-1,-1,185,-1,186,187,},{},{},{},{-1,189,192,196,200,203,-1,207,},{-1,-1,190,-1,191,},{},{},{-1,-1,-1,-1,-1,193,194,195,},{},{},{},{-1,-1,-1,197,198,-1,199,},{},{},{},{-1,-1,201,-1,202,},{},{},{-1,-1,-1,204,-1,205,206,},{},{},{},{},{-1,209,212,215,218,221,224,225,},{-1,-1,-1,-1,210,211,},{},{},{-1,-1,-1,-1,213,214,},{},{},{-1,-1,216,-1,217,},{},{},{-1,-1,-1,-1,219,220,},{},{},{-1,-1,-1,-1,222,223,},{},{},{},{-1,-1,226,-1,-1,227,},{},{},{-1,-1,229,230,231,232,233,},{},{},{},{},{},{},{-1,236,239,250,267,284,298,310,316,},{-1,-1,-1,-1,237,-1,238,},{},{},{-1,240,-1,241,242,243,246,247,},{},{},{},{-1,-1,-1,244,245,},{},{},{},{-1,-1,-1,-1,248,249,},{},{},{-1,-1,-1,251,254,257,260,263,266,},{-1,-1,-1,252,-1,253,},{},{},{-1,-1,255,256,},{},{},{-1,-1,-1,258,-1,259,},{},{},{-1,-1,-1,261,-1,262,},{},{},{-1,-1,-1,264,265,},{},{},{},{-1,268,271,274,277,280,281,},{-1,-1,-1,269,270,},{},{},{-1,-1,272,-1,273,},{},{},{-1,275,-1,-1,-1,-1,-1,276,},{},{},{-1,-1,278,-1,279,},{},{},{},{-1,-1,-1,-1,282,283,},{},{},{-1,285,286,289,290,293,296,297,},{},{-1,-1,-1,-1,287,-1,288,},{},{},{},{-1,-1,-1,291,292,},{},{},{-1,-1,-1,294,-1,-1,295,},{},{},{},{},{-1,-1,-1,299,300,303,304,307,},{},{-1,-1,-1,-1,301,302,},{},{},{},{-1,305,306,},{},{},{-1,-1,-1,308,-1,309,},{},{},{-1,-1,-1,311,312,313,314,315,},{},{},{},{},{},{},{-1,318,319,325,330,336,342,348,},{},{-1,-1,320,321,322,323,324,},{},{},{},{},{},{-1,-1,326,327,328,329,},{},{},{},{},{-1,331,332,333,334,335,},{},{},{},{},{},{-1,-1,337,338,339,340,341,},{},{},{},{},{},{-1,-1,-1,343,344,345,346,347,},{},{},{},{},{},{-1,-1,349,350,-1,351,},{},{},{},{-1,353,354,355,356,357,358,359,360,},{},{},{},{},{},{},{},{},{},};


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;
	if(n<=stala+1)
		return count_mushrooms1(n);
	int x = 0;
	while(graf[x].size()>0){
		int c = use_machine(zapytanie[x]);
//		wypiszvector(zapytanie[x]);
		x = graf[x][c];
	}
	x = maska[x];
	for(int i=0;i<stala;i++){
		if((x>>i)&1){
			A[1].push_back(i+1);
			Ac[1]++;
		}
		else{
			A[0].push_back(i+1);
			Ac[0]++;
		}
	}
	it = stala+1;
	return count_mushrooms1(n);
}

Subtask #1
81.8841 / 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 0 ms 464 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 4 ms 500 KB Output is correct
9 Correct 4 ms 756 KB Output is correct
10 Partially correct 4 ms 752 KB Output is partially correct
11 Partially correct 4 ms 504 KB Output is partially correct
12 Partially correct 4 ms 752 KB Output is partially correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 3 ms 480 KB Output is correct
15 Partially correct 4 ms 500 KB Output is partially correct
16 Partially correct 4 ms 504 KB Output is partially correct
17 Correct 3 ms 492 KB Output is correct
18 Correct 4 ms 508 KB Output is correct
19 Partially correct 4 ms 504 KB Output is partially correct
20 Partially correct 5 ms 752 KB Output is partially correct
21 Partially correct 4 ms 756 KB Output is partially correct
22 Partially correct 5 ms 756 KB Output is partially correct
23 Correct 4 ms 504 KB Output is correct
24 Correct 3 ms 492 KB Output is correct
25 Partially correct 4 ms 748 KB Output is partially correct
26 Partially correct 6 ms 504 KB Output is partially correct
27 Partially correct 4 ms 504 KB Output is partially correct
28 Partially correct 4 ms 508 KB Output is partially correct
29 Partially correct 4 ms 696 KB Output is partially correct
30 Partially correct 4 ms 504 KB Output is partially correct
31 Partially correct 4 ms 508 KB Output is partially correct
32 Partially correct 4 ms 508 KB Output is partially correct
33 Partially correct 4 ms 500 KB Output is partially correct
34 Partially correct 4 ms 512 KB Output is partially correct
35 Partially correct 4 ms 508 KB Output is partially correct
36 Partially correct 5 ms 504 KB Output is partially correct
37 Partially correct 5 ms 508 KB Output is partially correct
38 Partially correct 5 ms 500 KB Output is partially correct
39 Partially correct 4 ms 756 KB Output is partially correct
40 Partially correct 4 ms 756 KB Output is partially correct
41 Partially correct 4 ms 752 KB Output is partially correct
42 Partially correct 5 ms 468 KB Output is partially correct
43 Partially correct 5 ms 508 KB Output is partially correct
44 Partially correct 4 ms 508 KB Output is partially correct
45 Partially correct 4 ms 504 KB Output is partially correct
46 Partially correct 4 ms 500 KB Output is partially correct
47 Partially correct 4 ms 508 KB Output is partially correct
48 Partially correct 5 ms 500 KB Output is partially correct
49 Partially correct 4 ms 504 KB Output is partially correct
50 Partially correct 5 ms 740 KB Output is partially correct
51 Partially correct 4 ms 628 KB Output is partially correct
52 Partially correct 4 ms 504 KB Output is partially correct
53 Partially correct 4 ms 504 KB Output is partially correct
54 Partially correct 4 ms 756 KB Output is partially correct
55 Partially correct 4 ms 760 KB Output is partially correct
56 Partially correct 4 ms 504 KB Output is partially correct
57 Partially correct 4 ms 500 KB Output is partially correct
58 Partially correct 4 ms 504 KB Output is partially correct
59 Partially correct 4 ms 504 KB Output is partially correct
60 Partially correct 5 ms 496 KB Output is partially correct
61 Partially correct 5 ms 752 KB Output is partially 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 0 ms 344 KB Output is correct
66 Correct 0 ms 344 KB Output is correct
67 Correct 1 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 0 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 1 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