# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1035909 | Mr_Husanboy | Counting Mushrooms (IOI20_mushrooms) | C++17 | 6 ms | 600 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
template<typename T>
int len(T &a){return a.size();}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int count_mushrooms(int n) {
if(n < 226){
int ans = 1;
for(int i = 1; i < n; i ++){
ans += use_machine({0, i}) ^ 1;
}
return ans;
}
vector<int> a = {0}, b;
int i = 1;
while(len(a) < 2 && len(b) < 2){
if(use_machine({0, i})){
b.push_back(i);
}else{
a.push_back(i);
}
i ++;
}
int sq = 91;
while(len(a) < sq && len(b) < sq && i < n){
if(len(a) >= 2){
int cnt = use_machine({a[0], i, a[1], i + 1});
if(cnt == 0){
a.push_back(i);
a.push_back(i + 1);
}
if(cnt == 1){
a.push_back(i);
b.push_back(i + 1);
}
if(cnt == 2){
b.push_back(i);
a.push_back(i + 1);
}
if(cnt == 3){
b.push_back(i);
b.push_back(i + 1);
}
i += 2;
}else{
int cnt = use_machine({b[0], i, b[1], i + 1});
if(cnt == 3){
a.push_back(i);
a.push_back(i + 1);
}
if(cnt == 2){
a.push_back(i);
b.push_back(i + 1);
}
if(cnt == 1){
b.push_back(i);
a.push_back(i + 1);
}
if(cnt == 0){
b.push_back(i);
b.push_back(i + 1);
}
i += 2;
}
}
if(len(a) >= len(b)){
ll ans = len(a);
while(i < n){
vector<int> req;
for(int j = 0; j < len(a) && i < n; j ++){
req.push_back(a[j]);
req.push_back(i);
i ++;
}
int cnt = use_machine(req);
ans += len(req) / 2 - (cnt + 1) / 2;
if(cnt & 1){
b.push_back(req.back());
}else a.push_back(req.back());
}
return ans;
}else{
ll ans = len(a);
while(i < n){
vector<int> req;
for(int j = 0; j < len(b) && i < n; j ++){
req.push_back(b[j]);
req.push_back(i);
i ++;
}
int cnt = use_machine(req);
ans += (cnt + 1) / 2;
if(cnt & 1){
a.push_back(req.back());
}else b.push_back(req.back());
}
return ans;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |