| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 721507 | vjudge1 | 버섯 세기 (IOI20_mushrooms) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define N '\n';
#define VI <vector <int>>
#define VVI <vector <vector <int>>>
int count_mushrooms(int n){
int cnt = 1;
if(n <= 226){
for(int i = 1; i < n; i++){
cnt += 1 - use_machine({0, i});
}
return cnt;
}
vector <int> As = {0};
vector <int> Bs;
int mn = 10000, ans;
for(int i = 1; i < 500; i++){
if(2*i + ((n - (2*i)) / i) < mn){
mn = 2*i + ((n - (2*i)) / i);
ans = i;
}
}
int unt = ans*2;
// 188 - 1 = 187
for(int i = 1; i < unt; i++){
bool q = use_machine({0,i});
if(q)
Bs.push_back(i);
else
As.push_back(i);
}
cnt += As.size()-1;
int i = unt;
vector <int> Is;
// n - 188 / 94
if(As.size() >= Bs.size()){
for(; i < n;){
vector<int> search;
int j = 0;
for(; j < As.size() && i < n; j++ ){
search.push_back(i);
is.push_back(i);
search.push_back(As[j]);
i++;
}
int q = use_machine(search);
cnt += (search.size()/2) - ((q/2) +(q % 2));
if(q/2 + q % 2 == 0){
for(int i = 0; i < Is.size(); i++){
As.push_back(Is[i]);
}
}
}
}
else{
for(; i < n; ){
vector<int> search;
for(int j = 0; j < Bs.size() && i < n; j++){
search.push_back(i);
is.push_back(i);
search.push_back(Bs[j]);
i++;
}
int q = use_machine(search);
cnt += q/2 + q % 2;
if(q/2 + q % 2 == 0){
for(int i = 0; i < Is.size(); i++){
Bs.push_back(Is[i]);
}
}
}
}
// B A B A B A
// B A A A B A B A
return cnt;
}