Submission #312900

#	Time	Username	Problem	Language	Result	Execution time	Memory
312900		DanerZein	Counting Mushrooms (IOI20_mushrooms)	C++14	80.43 / 100	10 ms	896 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int punt[100000];
int hongos=280;
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;
  bool sw1=0;
  if(n==1) return 1;
  if(n==2){
    vi aux;
    aux.push_back(0);
    aux.push_back(1);
    if(!use_machine(aux)) return 2;
    else return 1;
  }
  //vi a,b;
  for(int i=1;i<=2;i++){
    vector<int> aux;
    aux.push_back(i);
    aux.push_back(0);
    if(!use_machine(aux)) pa.push_back(i);
    else pb.push_back(i);
  }
  if(pa.size()>pb.size()) sw1=1;
  for(int i=3;i<=min(hongos,n-1);i+=2){
    vector<int> aux;
    aux.push_back(i);
    if(sw1==1) aux.push_back(pa[0]);
    else aux.push_back(pb[0]);
    if(i+1<=min(hongos,n-1)) aux.push_back(i+1);
    if(sw1==1) aux.push_back(pa[1]);
    else aux.push_back(pb[1]);
    int y=use_machine(aux);
    // for(int j=0;j<aux.size();j++) cout<<aux[j]<<" ";
    //cout<<y<<endl;
    if(aux.size()==3){
      if(sw1==0){
	if(y==1)
	  pa.push_back(i);
	else
	  pb.push_back(i);
      }
      else{
	if(y==1) pb.push_back(i);
	else pa.push_back(i);
      }
    }
    else{
      if(sw1==1){
	if(y==0){
	  pa.push_back(i);
	  pa.push_back(i+1);
	}
	if(y==1){
	  pa.push_back(i+1);
	  pb.push_back(i);
	}
	if(y==2){
	  pa.push_back(i);
	  pb.push_back(i+1);
	}
	if(y==3){
	  pb.push_back(i);
	  pb.push_back(i+1);
	}
      }
      else{
	if(y==0){
	  pb.push_back(i+1);
	  pb.push_back(i);
	}
	if(y==1){
	  pa.push_back(i);
	  pb.push_back(i+1);
	}
	if(y==2){
	  pb.push_back(i);
	  pa.push_back(i+1);
	}
	if(y==3){
	  pa.push_back(i);
	  pa.push_back(i+1);
	}
      }
    }
    //if(pa.size()==2 or pb.size()==2) break;
  }
  ca=pa.size();
  res=ca;
  cb=pb.size();
  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: 80.427 / 100