Submission #312867

#	Time	Username	Problem	Language	Result	Execution time	Memory
312867		DanerZein	Counting Mushrooms (IOI20_mushrooms)	C++14	25 / 100	31 ms	912 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int punt[100000];
int hongos=2000;
void crear(int n,bool sw){
  if(sw==1){
    int p=n;
    punt[0]=n;
    int j=1;
    while(true){
      p--;
      punt[j]=punt[j+1]=p;
      j+=2;
      if(p==0) break;
    }
  }
  else{
    int p=0;
    punt[0]=0;
    int j=1;
    while(true){
      p++;
      punt[j]=punt[j+1]=p;
      j+=2;
      if(p==n) break;
    }
  }
}
int count_mushrooms(int n) {
  int res=1;
  int ca,cb;
  vi pa,pb;
  pa.push_back(0);
  ca=cb=0;
  for(int i=1;i<=min(hongos,n-1);i++){
    vector<int> aux;
    aux.push_back(0);
    aux.push_back(i);
    //cout<<use_machine(aux)<<" "<<i<<endl;
    if(use_machine(aux)){
      cb++;
      pb.push_back(i);
    }
    else{
      ca++;
      res++;
      pa.push_back(i);
    }
    //if(pa.size()==2 or pb.size()==2) break;
  }
  ca++;
  memset(punt,0,sizeof punt);
  bool sw=0;
  if(ca>=cb) sw=1;
  int c=max(ca,cb);
  crear(c,sw);
  //for(int i=0;i<=4;i++) cout<<punt[i]<<" ";
  //cout<<endl;
  for(int i=hongos+1;i<n;i+=c){
    vector<int> aux;
    if(i+c>=n){
      int h=n-i;
      crear(h,sw);
    }
    for(int j=0;j<c;j++){
      if(i+j<n)aux.push_back(i+j);
      if(sw==1)
	aux.push_back(pa[j]);
      else
	aux.push_back(pb[j]);
    }
    //for(int j=0;j<aux.size();j++) cout<<aux[j]<<" ";
    //cout<<endl;
    //cout<<punt[use_machine(aux)]<<endl;
    res+=(punt[use_machine(aux)]);
  }
  //  cout<<res<<endl;
  return res;
}

• Subtask 1: 25 / 100