| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 409374 | Carmel_Ab1 | 버섯 세기 (IOI20_mushrooms) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "mushrooms.h"
#include "stub.cpp"
using namespace std;
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
int ceil(int a,int b){
int ans=a/b;
if(a%b)
ans++;
return ans;
}
int count_mushrooms(int n) {
int ans=1;
vi o,z,a(n,-1);
a[0]=0;
z.pb(0);
if(n<=226){
for(int i=2; i<n; i++)
ans+=1- use_machine({0,i});
return ans;
}
if(use_machine({0,1})){
o.pb(1);
a[1]=1;
}
else{
ans++;
a[1]=0;
z.pb(0);
}
if(use_machine({0,2})){
o.pb(2);
a[2]=1;
}
else {
ans++;
a[2] = 0;
z.pb(2);
}
int first=1;
const int k=100;
bool z2=z.size()==2;
for(int i=3;z2 && o.size()<k && z.size()<k;first+=2, i+=2){
int res= use_machine({z[0],i,z[1],i+1});
if(res==0){
ans+=2;
z.pb(i);
z.pb(i+1);
a[i]=a[i+1]=0;
}
else if(res==1){
ans++;
z.pb(i);
o.pb(i+1);
a[i]=0,a[i+1]=1;
}
else if(res==2){
ans++;
o.pb(i);
z.pb(i+1);
a[i]=1,a[i+1]=0;
}
else if(res==3){
o.pb(i);
o.pb(i+1);
a[i]=1,a[i+1]=1;
}
}
for(int i=3;!z2 && o.size()<k && z.size()<k;first+=2, i+=2){
int res= use_machine({o[0],i,o[1],i+1});
if(res==0){
o.pb(i);
o.pb(i+1);
a[i]=a[i+1]=1;
}
else if(res==1){
ans++;
o.pb(i);
z.pb(i+1);
a[i]=1,a[i+1]=0;
}
else if(res==2){
ans++;
z.pb(i);
o.pb(i+1);
a[i]=0,a[i+1]=1;
}
else if(res==3){
ans+=2;
z.pb(i);
z.pb(i+1);
a[i]=0,a[i+1]=0;
}
}
vi left;
for(int i=0; i<n;i++)
if(a[i]==-1)
left.pb(i);
if(o.size()>z.size()){
for(int i=first,j=0; i<n;j=0, i++){
if(a[i]!=-1)continue;
vi cur;
while(left.size() && cur.size()+2<=n && j<o.size()){
cur.pb(o[j]);
cur.pb(left.back());
left.pop_back();
j++;
}
if(cur.size()>=2)
ans+= ceil(use_machine(cur),2);
}
}
else{
for(int i=first,j=0; i<n;j=0, i++){
if(a[i]!=-1)continue;
int in=0;
vi cur;
while(left.size() && cur.size()+2<=n && j<z.size()){
cur.pb(z[j]);
cur.pb(left.back());
left.pop_back();
j++;
in++;
}
if(cur.size()>=2)
ans+= in-ceil(use_machine(cur),2);
}
}
return ans;
}