제출 #643390

#제출 시각아이디문제언어결과실행 시간메모리
643390jamezzz버섯 세기 (IOI20_mushrooms)C++17
100 / 100
9 ms468 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; #define pb push_back int M=103; int pop(vector<int> &v){ int x=v.back(); v.pop_back(); return x; } int count_mushrooms(int n){ vector<int> v[2],u; v[0]={0}; for(int i=n-1;i>0;--i)u.pb(i); if(n<=227){ while(!u.empty()){ int x=pop(u); if(use_machine({0,x})==1)v[1].pb(x); else v[0].pb(x); } return v[0].size(); } //phase 1 for(int i=0;i<2;++i){ int x=pop(u); if(use_machine({0,x})==1)v[1].pb(x); else v[0].pb(x); } int i=0; if(v[0].size()<2)i=1; int x=pop(u),y=pop(u); int res=use_machine({v[i][0],x,v[i][1],y}); if(res==0)v[i].pb(x),v[i].pb(y); else if(res==1)v[i].pb(x),v[1-i].pb(y); else if(res==2)v[1-i].pb(x),v[i].pb(y); else v[1-i].pb(x),v[1-i].pb(y); /* printf("a: "); for(int x:v[0])printf("%d ",x); printf("\n"); printf("b: "); for(int x:v[1])printf("%d ",x); printf("\n"); */ //phase 2 bool bad=false; while(v[0].size()+v[1].size()<2*M-1){ int x=pop(u),y=pop(u),z=pop(u); if(bad){//y and z are different int i=0; if(v[0].size()<3)i=1; int res=use_machine({v[i][0],x,v[i][1],y,v[i][2],z}); if(res==0)v[i].pb(x),v[i].pb(y),v[i].pb(z); else if(res==1)v[i].pb(x),v[i].pb(y),v[1-i].pb(z); else if(res==2)v[i].pb(x),v[1-i].pb(y),v[i].pb(z); else if(res==3)v[1-i].pb(x),v[i].pb(y),v[1-i].pb(z); else if(res==4)v[1-i].pb(x),v[1-i].pb(y),v[i].pb(z); else v[1-i].pb(x),v[1-i].pb(y),v[1-i].pb(z); bad=false; } else{ int i=0; if(v[0].size()<3)i=1; int res=use_machine({v[i][0],x,v[i][1],y,v[i][2],z}); if(res==0)v[i].pb(x),v[i].pb(y),v[i].pb(z); else if(res==1)v[i].pb(x),v[i].pb(y),v[1-i].pb(z); else if(res==2)bad=true,v[i].pb(z); else if(res==3)bad=true,v[1-i].pb(z); else if(res==4)v[1-i].pb(x),v[1-i].pb(y),v[i].pb(z); else v[1-i].pb(x),v[1-i].pb(y),v[1-i].pb(z); } /* printf("%d %d %d\n",x,y,z); printf("bad: %d\n",bad); printf("a: "); for(int x:v[0])printf("%d ",x); printf("\n"); printf("b: "); for(int x:v[1])printf("%d ",x); printf("\n"); */ if(!bad)continue; if(min(v[0].size(),v[1].size())<2){ z=pop(u); u.pb(x),u.pb(y),u.pb(z); } else{ int z=pop(u),w=pop(u); int i=0; if(v[0].size()<3)i=1; int res=use_machine({v[1-i][0],x,v[1-i][1],v[i][0],y,v[i][1],z,v[i][2],w}); if(res==1)v[1-i].pb(x),v[i].pb(y),v[i].pb(z),v[i].pb(w); else if(res==2)v[1-i].pb(x),v[i].pb(y),v[i].pb(z),v[1-i].pb(w); else if(res==3)v[1-i].pb(x),v[i].pb(y),v[1-i].pb(z),v[i].pb(w); else if(res==4)v[1-i].pb(x),v[i].pb(y),v[1-i].pb(z),v[1-i].pb(w); else if(res==5)v[i].pb(x),v[1-i].pb(y),v[i].pb(z),v[i].pb(w); else if(res==6)v[i].pb(x),v[1-i].pb(y),v[i].pb(z),v[1-i].pb(w); else if(res==7)v[i].pb(x),v[1-i].pb(y),v[1-i].pb(z),v[i].pb(w); else v[i].pb(x),v[1-i].pb(y),v[1-i].pb(z),v[1-i].pb(w); bad=false; } } //phase 3 int extra[2]={0,0}; while(!u.empty()){ int i=0; if(v[0].size()<v[1].size())i=1; int t=min(v[i].size(),u.size()); vector<int> m; for(int x=0;x<t;++x){ m.pb(v[i][x]);m.pb(pop(u)); } int res=use_machine(m); if(res%2==1)v[1-i].pb(m.back()); else v[i].pb(m.back()); extra[i]+=(t-1)-res/2,extra[1-i]+=res/2; } return v[0].size()+extra[0]; }

컴파일 시 표준 에러 (stderr) 메시지

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:55:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |  while(v[0].size()+v[1].size()<2*M-1){
      |        ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...