Submission #308788

#	Time	Username	Problem	Language	Result	Execution time	Memory
308788		chubyxdxd	Counting Mushrooms (IOI20_mushrooms)	C++17	80.43 / 100	12 ms	512 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
int count_mushrooms(int n){
	vector<int> A;
	vector<int> B;
	stack<int> C;
	A.pb(0);
	for(int i=1;i<n;i++)C.push(i);
	while(A.size()<141 and B.size()<141 and !C.empty()){
	  if(C.size()==1){
	    int x=C.top();
	    C.pop();
	    int f=use_machine({0,x});
	    if(f==0)A.pb(x);
	    else B.pb(x);
	    continue;
	  }
	  if(A.size()>=2){
	    int x=C.top();C.pop();
	    int y=C.top();C.pop();
	    int f=use_machine({x,A[0],y,A[1]});
	    if(f==0){
	      A.pb(x);
	      A.pb(y);
	    }
	    if(f==1){
	      B.pb(x);
	      A.pb(y);
	    }
	    if(f==2){
	      A.pb(x);
	      B.pb(y);
	    }
	    if(f==3){
	      B.pb(x);
	      B.pb(y);
	    }
	  }
	  else if(B.size()>=2){
	    int x=C.top();C.pop();
	    int y=C.top();C.pop();
	    int f=use_machine({x,B[0],y,B[1]});
	    if(f==0){
	      B.pb(x);
	      B.pb(y);
	    }
	    if(f==1){
	      A.pb(x);
	      B.pb(y);
	    }
	    if(f==2){
	      B.pb(x);
	      A.pb(y);
	    }
	    if(f==3){
	      A.pb(x);
	      A.pb(y);
	    }
	  }
	  else{
	    int x=C.top();C.pop();
	    int t=use_machine({0,x});
	    if(t==1)B.pb(x);
	    else A.pb(x);
	  }
	}
	if(A.size()>=B.size()){
	  int ans=n-B.size();
	  while(!C.empty()){
	    int j=0;
	    vector<int> m;
	    while(j<A.size() and !C.empty()){
	      int x=C.top();C.pop();
	      m.pb(x);
	      m.pb(A[j]);
	      j++;
	    }
	    int f=use_machine(m);
	    f=(f+1)/2;
	    ans-=f;
	  }
	  return ans;
	}
	else{
	  int ans=A.size();
	  while(!C.empty()){
	    int j=0;
	    vector<int> m;
	    while(j<B.size() and !C.empty()){
	      int x=C.top();C.pop();
	      m.pb(x);
	      m.pb(B[j]);
	      j++;
	    }
	    int f=use_machine(m);
	    f=(f+1)/2;
	    ans+=f;
	  }
	  return ans;
	}
	return 0;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:75:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |      while(j<A.size() and !C.empty()){
      |            ~^~~~~~~~~
mushrooms.cpp:92:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |      while(j<B.size() and !C.empty()){
      |            ~^~~~~~~~~

• Subtask 1: 80.427 / 100