# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1021604 | Ahmed_Solyman | 버섯 세기 (IOI20_mushrooms) | C++14 | 2 ms | 344 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
In the name of Allah
made by: Ahmed_Solyman
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int use_machine(vector<int>x);
int count_mushrooms(int n){
if(n<=226){
int ret=1;
for(int i=1;i<n;i++){
ret+=1-use_machine({0,i});
}
return ret;
}
int ret=0,k=94;
vector<int>v[2];
v[0].push_back(0);
for(int i=1;i<=2;i++){
if(use_machine({0,i})==0)v[0].push_back(i);
else v[1].push_back(i);
}
bool typ;
int x,y;
if(v[0].size()>=2){
typ=0;
x=v[0][0];y=v[0][1];
}
else{
typ=1;
x=v[1][0];y=v[1][1];
}
for(int i=3;i<=2*k-2;i+=2){
int h=use_machine({x,i,y,i+1});
if(h==0){
v[typ].push_back(i);
v[typ].push_back(i+1);
}
if(h==1){
v[typ^1].push_back(i);
v[typ].push_back(i+1);
}
if(h==2){
v[typ].push_back(i);
v[typ^1].push_back(i+1);
}
if(h==3){
v[typ^1].push_back(i);
v[typ^1].push_back(i+1);
}
}
auto f=[&](int l,int r){
vector<int>p;
vector<int>&g=(v[0].size()>v[1].size()?v[0]:v[1]);
if(v[0].size()>v[1].size())typ=0;
else typ=1;
assert(r-l+1<=(int)g.size());
for(int i=l;i<=r;i++){
p.push_back(i);
p.push_back(g[i-l]);
}
int u=use_machine(p);
if(u&1)v[typ^1].push_back(l);
else v[typ].push_back(l);
u=(u+1)/2;
if(typ)return u;
else return r-l+1-u;
};
ret=(int)v[0].size();
int mx=max(v[0].size(),v[1].size());
int i=2*k-1;
while(i<n){
ret+=f(i,min(i+mx-1,n-1));
i=min(i+mx-1,n-1)+1;
mx=max(v[0].size(),v[1].size());
}
return ret;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |