oj.uz

Submission #468860

# Submission time Handle Problem Language Result Execution time Memory
468860 2021-08-30T02:45:21 Z vector Counting Mushrooms (IOI20_mushrooms) C++17
100 / 100
 10 ms 340 KB 
#include "mushrooms.h"
#include <bits/stdc++.h>
#define BUCKET 200
using namespace std;
vector<int> A[3];
int count_mushrooms(int N)
{
    int ret=0, idx=5, z, x, b[5];
	vector<int> v;
	A[0].push_back(0);
	if (N<=2*BUCKET) {
        for (int i=1; i<N-1; i+=2) {
            v.push_back(i); v.push_back(0); v.push_back(i+1); z=use_machine(v); v.clear();
            ret+=z;
        }
        if (N%2==0) {
            v.push_back(N-1); v.push_back(0); z=use_machine(v); v.clear();
            ret+=z;
        }
        return N-ret;
	}
	v.push_back(0); v.push_back(1); z=use_machine(v); v.clear();
	if (z==1) A[1].push_back(1);
	else A[0].push_back(1);
	v.push_back(0); v.push_back(2); z=use_machine(v); v.clear();
	if (z==1) A[1].push_back(2);
	else A[0].push_back(2);
	if (A[0].size()>=2) {
        v.push_back(A[0][0]); v.push_back(3); v.push_back(A[0][1]); v.push_back(4); z=use_machine(v); v.clear();
        if (z>=2) A[1].push_back(3);
        else A[0].push_back(3);
        if (z%2==1) A[1].push_back(4);
        else A[0].push_back(4);
	}
	else {
        v.push_back(A[1][0]); v.push_back(3); v.push_back(A[1][1]); v.push_back(4); z=use_machine(v); v.clear();
        if (z>=2) A[0].push_back(3);
        else A[1].push_back(3);
        if (z%2==1) A[0].push_back(4);
        else A[1].push_back(4);
	}
	for (int i=5; i<BUCKET; i+=5) {
        for (int j=0; j<5; j++) b[j]=i+j;
        if (A[0].size()>=3) x=0;
        else x=1;
        v.push_back(A[x][0]); v.push_back(b[0]); v.push_back(A[x][1]); v.push_back(b[1]); v.push_back(A[x][2]); v.push_back(b[2]); z=use_machine(v); v.clear();
        if (z%2==1) A[1-x].push_back(b[2]);
        else A[x].push_back(b[2]);
        z-=z%2;
        if (z%4==0) {
            if (z==0) {
                A[x].push_back(b[0]);
                A[x].push_back(b[1]);
            }
            if (z==4) {
                A[1-x].push_back(b[0]);
                A[1-x].push_back(b[1]);
            }
            v.push_back(A[x][0]); v.push_back(b[3]); v.push_back(A[x][1]); v.push_back(b[4]); z=use_machine(v); v.clear();
            if (z>=2) A[1-x].push_back(b[3]);
            else A[x].push_back(b[3]);
            if (z%2==1) A[1-x].push_back(b[4]);
            else A[x].push_back(b[4]);
        }
        else {
            assert(z==2);
            if (min(A[0].size(), A[1].size())>=2) {
                v.push_back(A[1-x][0]); v.push_back(b[0]); v.push_back(A[1-x][1]); v.push_back(A[x][0]); v.push_back(b[1]); v.push_back(A[x][1]); v.push_back(b[3]); v.push_back(A[x][2]); v.push_back(b[4]); z=use_machine(v); v.clear();
                if (z%2==0) A[1-x].push_back(b[4]);
                else A[x].push_back(b[4]);
                if (z%2==0) z--;
                if (z>=4) {
                    assert(z==5 || z==7);
                    A[x].push_back(b[0]);
                    A[1-x].push_back(b[1]);
                    if (z==5) A[x].push_back(b[3]);
                    else A[1-x].push_back(b[3]);
                }
                else {
                    assert(z==1 || z==3);
                    A[1-x].push_back(b[0]);
                    A[x].push_back(b[1]);
                    if (z==1) A[x].push_back(b[3]);
                    else A[1-x].push_back(b[3]);
                }
            }
            else {
                v.push_back(A[x][0]); v.push_back(b[0]); z=use_machine(v); v.clear();
                if (z==1) {
                    A[1-x].push_back(b[0]);
                    A[x].push_back(b[1]);
                }
                else {
                    A[x].push_back(b[0]);
                    A[1-x].push_back(b[1]);
                }
                v.push_back(A[x][0]); v.push_back(b[3]); v.push_back(A[x][1]); v.push_back(b[4]); z=use_machine(v); v.clear();
                if (z>=2) A[1-x].push_back(b[3]);
                else A[x].push_back(b[3]);
                if (z%2==1) A[1-x].push_back(b[4]);
                else A[x].push_back(b[4]);
            }
        }
	}
	idx=BUCKET;
    while (idx<N) {
        if (A[0].size()>=A[1].size()) {
            for (int i=0; i<A[0].size(); i++) {
                v.push_back(idx++);
                v.push_back(A[0][i]);
                if (idx==N) break;
            }
            z=use_machine(v);
            ret+=z/2;
            if (z%2) A[1].push_back(v[0]);
            else A[0].push_back(v[0]);
        }
        else {
            for (int i=0; i<A[1].size(); i++) {
                v.push_back(idx++);
                v.push_back(A[1][i]);
                if (idx==N) break;
            }
            z=use_machine(v);
            ret+=v.size()/2-1-z/2;
            if (z%2) A[0].push_back(v[0]);
            else A[1].push_back(v[0]);
        }
        v.clear();
	}
	return N-ret-A[1].size();
}

Compilation message

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:108:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             for (int i=0; i<A[0].size(); i++) {
      |                           ~^~~~~~~~~~~~
mushrooms.cpp:119:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             for (int i=0; i<A[1].size(); i++) {
      |                           ~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

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