Submission #309451

#	Time	Username	Problem	Language	Result	Execution time	Memory
309451		lucaperju	Counting Mushrooms (IOI20_mushrooms)	C++14	90.04 / 100	12 ms	544 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ta,tb,ord;
vector<int>vc;
int v[20003];
int count_mushrooms(int n) {
	std::vector<int> m;
	/**
	for (int i = 0; i < n; i++)
		m.push_back(i);
	int c1 = use_machine(m);
	m = {0, 1};
	int c2 = use_machine(m);
	return c1+c2;
	*/
	int i,j;
    for(i=1;i<n;++i)
        ord.push_back(i);
    srand(time(NULL));
    random_shuffle(ord.begin(),ord.end());
    ta.push_back(0);
    i=0;
    while(i<ord.size() && ta.size()<2 && tb.size()<2)
    {
        m.clear();
        m.push_back(0);
        m.push_back(ord[i]);
        int a = use_machine(m);
        if(a==0)
            ta.push_back(ord[i]);
        else
            tb.push_back(ord[i]);
        ++i;
    }
    int type=1;
    if(ta.size()<2)
        type=2;
    if(ta.size()>=2)
    {
        vc.push_back(ta[0]);
        vc.push_back(ta[1]);
    }
    else
    {
        vc.push_back(tb[0]);
        vc.push_back(tb[1]);
    }
    int cnta=0;
    int cntc=95;
    while(cntc--)
    {
        if(i+1<ord.size())
        {
            m.clear();
            m.push_back(vc[0]);
            m.push_back(ord[i]);
            m.push_back(vc[1]);
            m.push_back(ord[i+1]);
            int a=use_machine(m);
            if(type==1)
            {
                if(a&2)
                    tb.push_back(ord[i]);
                else
                    ta.push_back(ord[i]);
                if(a&1)
                    tb.push_back(ord[i+1]);
                else
                    ta.push_back(ord[i+1]);
            }
            else
            {
                if(a&2)
                    ta.push_back(ord[i]);
                else
                    tb.push_back(ord[i]);
                if(a&1)
                    ta.push_back(ord[i+1]);
                else
                    tb.push_back(ord[i+1]);
            }
            i+=2;
        }
        else if(i<ord.size())
        {
            m.clear();
            m.push_back(0);
            m.push_back(ord[i]);
            int a = use_machine(m);
            if(a==0)
                ta.push_back(ord[i]);
            else
                tb.push_back(ord[i]);
            ++i;
        }
        else
            break;
    }
    if(ta.size()>tb.size())
        type=1;
    else
        type=2;
    vc.clear();
    if(type==1)
        for(j=0;j<ta.size();++j)
            vc.push_back(ta[j]);
    else
        for(j=0;j<tb.size();++j)
            vc.push_back(tb[j]);
    cnta=ta.size();
    while(i<ord.size())
    {
        m.clear();
        int catc=0;
        int last;
        for(j=0;j<vc.size() && i<ord.size();++j,++i)
        {
            m.push_back(vc[j]);
            m.push_back(ord[i]);
            ++catc;
            last=ord[i];
        }
        int a=use_machine(m);
        int ok=(a&1);
        a=((a+1)>>1);
        if(ok==0)
            vc.push_back(last);
        if(type==2)
            cnta+=a;
        else
            cnta+=catc-a;
    }
    return cnta;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:24:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     while(i<ord.size() && ta.size()<2 && tb.size()<2)
      |           ~^~~~~~~~~~~
mushrooms.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if(i+1<ord.size())
      |            ~~~^~~~~~~~~~~
mushrooms.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         else if(i<ord.size())
      |                 ~^~~~~~~~~~~
mushrooms.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(j=0;j<ta.size();++j)
      |                 ~^~~~~~~~~~
mushrooms.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(j=0;j<tb.size();++j)
      |                 ~^~~~~~~~~~
mushrooms.cpp:112:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     while(i<ord.size())
      |           ~^~~~~~~~~~~
mushrooms.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(j=0;j<vc.size() && i<ord.size();++j,++i)
      |                 ~^~~~~~~~~~
mushrooms.cpp:117:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(j=0;j<vc.size() && i<ord.size();++j,++i)
      |                                ~^~~~~~~~~~~

• Subtask 1: 90.0398 / 100