| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1356812 | Sacharlemagne | 비스킷 담기 (IOI20_biscuits) | C++20 | 0 ms | 0 KiB |
#include "mushrooms.h"
using namespace std;
typedef vector<int> vi;
int queryOne(int ind) {
return 1-use_machine(vi{0, ind});
}
int naive(int n) {
int ans = 0;
for (int i = 1; i<n; ++i) ans += queryOne(i);
return ans+1;
}
int count_mushrooms(int n) {
if (n < 3) return naive(n);
vi temp(3); temp[0] = 1;
for (int i = 1; i<2; ++i) temp[i] = queryOne(i);
int a, b;
bool As = (temp[1] + temp[2]);
As ? (a = temp[1], b = temp[2]) : (a = 0, b = (temp[1] ? 1 : 2));
vi trans = As ? (vi){2, 1, 1, 0} : (vi){0, 1, 2, 2};
int ans = 1 + temp[1] + temp[2] + queryOne(3);
for (int i = 4; i<n-1; i += 2) {
int val = use_machine((vi){i, a, i+1, b});
ans += trans[val];
}
if (n % 2 == 1) ans += queryOne(n-1);
return ans;
}
