Submission #468860

#	Time	Username	Problem	Language	Result	Execution time	Memory
468860		vector	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	10 ms	340 KiB

mushrooms

#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 (stderr)

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 / 100