| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 432609 | Andyvanh1 | Counting Mushrooms (IOI20_mushrooms) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#define vt vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,x) for(int (i) = 0; (i) < (x); (i)++)
typedef long long ll;
typedef long double ld;
typedef vt<int> vi;
typedef pair<int,int> pii;
int naive(int n){
int ans = 1;
for(int i = 1; i < n; i++){
ans+=use_machine({0,i})^1;
}return ans;
}
int count_mushrooms(int n){
if(n<=100)return naive(n);
int h1;
int h2;
if(n==2){
return 2-use_machine({0,1});
}
int val1 = use_machine({0,1});
int val2 = use_machine({0,2});
bool bol = true;
if(val1==val2&&val1==1)h1 = 1, h2 = 2, bol = false;
else {
h1 = 0;
if(!val1)h2=1;
else h2 = 2;
}
int k = min(130,sqrt(n));
vi count1 = {0};
vi count2;
if(!val1)count1.pb(1);
else count2.pb(1);
if(!val2)count1.pb(2);
else count2.pb(2);
for(int i = 3; i < 2*k; i+=2){
int a = use_machine({h1,i,h2,i+1});
if(a==0){
if(bol){
count1.pb(i);
count1.pb(i+1);
}else{
count2.pb(i);
count2.pb(i+1);
}
}else if(a==1){
if(bol){
count1.pb(i);
count2.pb(i+1);
}else{
count2.pb(i);
count1.pb(i+1);
}
}else if(a==2){
if(bol){
count2.pb(i);
count1.pb(i+1);
}else{
count1.pb(i);
count2.pb(i+1);
}
}else{
if(bol){
count2.pb(i);
count2.pb(i+1);
}else{
count1.pb(i);
count1.pb(i+1);
}
}
}
int ans = count1.size();
int delta = 0;
for(int i = 2*k+1; i < n; i+=max(count1.size(),count2.size())-delta){
int prr = max(count1.size(), count2.size());
if(n-i<max(count1.size(),count2.size())){
if(count2.size()>count1.size()){
vi cur;
for(int j = 0; j < n-i; j++){
cur.pb(j+i);
cur.pb(count2[j]);
}
int a = use_machine(cur);
return ans + (a+1)/2;
}else{
vi cur;
for(int j = 0; j < n-i; j++){
cur.pb(j+i);
cur.pb(count1[j]);
}
int a = use_machine(cur);
return ans + n-i-(a+1)/2;
}
}else{
if(count2.size()>count1.size()){
vi cur;
for(int j = 0; j < count2.size(); j++){
cur.pb(j+i);
cur.pb(count2[j]);
}
int a = use_machine(cur);
ans+=(a+1)/2;
if(a%2==0){
count2.pb(i);
}else{
count1.pb(i);
}
}else{
vi cur;
for(int j = 0; j < count1.size(); j++){
cur.pb(j+i);
cur.pb(count1[j]);
}
int a = use_machine(cur);
ans+=count1.size()-(a+1)/2;
if(a%2==0){
count1.pb(i);
}else{
count2.pb(i);
}
}
}
delta = max(count1.size(),count2.size())-prr;
}
return ans;
}