| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 312984 | kobus | 버섯 세기 (IOI20_mushrooms) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define MAXN 1123
#define INF (int)1.5e12
#define INFF LLONG_MAX/2
#define eps 1e-4
int use_machine(int x[]);
int count_mushrooms(int n){
vector<int> s[2]={{0},{}};
int nn[2]={0,0};
vector<int> ns;
for(int i=1;i<n;i++)ns.pb(i);
int k=85;
while(ns.size()>0){
if(k>0 && ns.size()>1 && max(s[0].size(),s[1].size())>1){
k--;
int a=ns[ns.size()-1];
int b=ns[ns.size()-2];
ns.pop_back();
ns.pop_back();
bool si=1;
if(s[0].size()>s[1].size())si=0;
int v[4]={s[si][0],a,s[si][1],b};
int x=use_machine(v);
if(x%2)s[!si].pb(b);
else s[si].pb(b);
x=x/2;
if(x%2)s[!si].pb(a);
else s[si].pb(a);
}
else{
bool si=1;
if(s[0].size()>s[1].size())si=0;
int tam=min(s[si].size(),ns.size());
int v[2*tam];
for(int i=0;i<tam;i++){
v[2*i]=s[si][i];
}
for(int i=0;i<tam;i++){
v[2*i+1]=ns[ns.size()-i-1];
}
for(int i=0;i<tam;i++)ns.pop_back();
int x=use_machine(v);
if(x%2)s[!si].pb(v[2*tam-1]);
else s[si].pb(v[2*tam-1]);
x=x/2;
nn[!si]+=x;
nn[si]+=tam-1-x;
}
}
return s[0].size()+nn[0];
}