# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
534205 | benson1029 | Counting Mushrooms (IOI20_mushrooms) | C++14 | 10 ms | 460 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 "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int N;
int ans[6000];
int f[20];
vector< vector<int> > query[20], realQuery[20];
vector<int> temp;
vector<int> knownA, knownB;
int rPtr, lPtr;
int findQueryValue(vector<int> v) {
vector<int> v2;
v2.clear();
for(int i=0; i<v.size(); i++) {
if(knownA.size()>knownB.size()) v2.push_back(knownA[i]);
else v2.push_back(knownB[i]);
v2.push_back(v[i]+lPtr);
}
if(knownA.size()>knownB.size()) v2.push_back(knownA[v.size()]);
else v2.push_back(knownB[v.size()]);
v2.push_back(rPtr);
int rv = use_machine(v2);
if(knownB.size()>=knownA.size()) rv=v2.size()-1-rv;
if(rv%2==1) {
ans[rPtr] = 1;
knownB.push_back(rPtr);
} else {
ans[rPtr] = 0;
knownA.push_back(rPtr);
}
rPtr--;
return rv/2;
}
void solve(int lv, int l, vector<int> qAns) {
vector<int> A, B;
A.clear(); B.clear();
if(lv==0) {
ans[l] = qAns[0];
return;
}
int ctr = 0;
int sum = 0;
for(int i=2; i<qAns.size(); i+=2) {
// use of qAns[0], qAns[i-1] and qAns[i] to derive
ans[l+f[lv-1]*2+ctr] = (qAns[i-1] - qAns[i] + qAns[0]) % 2;
B.push_back((qAns[i-1] - qAns[i] + qAns[0]) / 2);
A.push_back((qAns[i-1] + qAns[i] - qAns[0]) / 2);
sum += ans[l+f[lv-1]*2+ctr];
ctr++;
}
B.push_back(qAns[0]);
A.push_back(qAns[qAns.size()-1] - qAns[0] - sum);
solve(lv-1, l, A);
solve(lv-1, l+f[lv-1], B);
}
void initFirstPhase() {
f[0] = 1;
for(int i=1; i<=10; i++) {
f[i] = f[i-1] * 2 + (1<<(i-1)) - 1;
}
query[0] = {{0}};
realQuery[0] = {{0}};
for(int i=1; i<=6; i++) {
// find the queries for i from i-1
temp.clear();
for(int j=f[i-1]; j<2*f[i-1]; j++) temp.push_back(j);
query[i].push_back(temp);
int cnt = 0;
for(int j=0; j<query[i-1].size()-1; j++) {
temp.clear();
for(int k:query[i-1][j]) temp.push_back(k);
for(int k:query[i-1][j]) temp.push_back(k+f[i-1]);
temp.push_back(f[i-1]*2+cnt);
query[i].push_back(temp);
temp.clear();
for(int k:query[i-1][j]) temp.push_back(k);
int ptr = 0;
for(int k=0; k<f[i-1]; k++) {
if(ptr<query[i-1][j].size() && query[i-1][j][ptr]==k) ptr++;
else temp.push_back(k+f[i-1]);
}
query[i].push_back(temp);
cnt++;
}
realQuery[i] = query[i];
temp.clear();
for(int j=0; j<f[i]; j++) temp.push_back(j);
query[i].push_back(temp);
temp.clear();
for(int j=0; j<f[i-1]; j++) temp.push_back(j);
for(int j=f[i-1]*2; j<f[i]; j++) temp.push_back(j);
realQuery[i].push_back(temp);
}
}
void initQuery() {
knownA.clear();
knownB.clear();
knownA.push_back(0);
lPtr = 3;
rPtr = 301;
ans[1] = 0;
for(int i=1; i<=301; i++) ans[i] = -1;
int tmp;
tmp = use_machine({0, 1});
if(tmp==1) {
ans[1] = 1;
knownB.push_back(1);
} else {
ans[1] = 0;
knownA.push_back(1);
}
tmp = use_machine({0, 2});
if(tmp==1) {
ans[2] = 1;
knownB.push_back(2);
} else {
ans[2] = 0;
knownA.push_back(2);
}
}
void apply(int lv) {
temp.clear();
for(int i=0; i<query[lv].size(); i++) {
temp.push_back(findQueryValue(realQuery[lv][i]));
}
if(lv>0) temp[temp.size()-1] += temp[0];
solve(lv, lPtr, temp);
for(int i=lPtr; i<lPtr+f[lv]; i++) {
if(ans[i]==1) {
knownB.push_back(i);
} else {
knownA.push_back(i);
}
}
lPtr += f[lv];
}
void Phase1() {
initFirstPhase();
initQuery();
apply(0);
apply(1);
apply(2);
apply(2);
apply(4);
apply(5);
apply(5);
}
int Phase2(int ptr) {
int ans = 0;
while(ptr < N) {
int rv = 0;
temp.clear();
if(knownA.size() > knownB.size()) {
for(int i=0; i<knownA.size(); i++) {
if(ptr==N) break;
temp.push_back(knownA[i]);
if(ptr<N) {
temp.push_back(ptr);
ptr++;
}
}
rv = temp.size()-1 - use_machine(temp);
ans += rv/2;
if(rv%2==0) {
knownB.push_back(ptr-1);
} else {
knownA.push_back(ptr-1);
}
} else {
for(int i=0; i<knownB.size(); i++) {
if(ptr==N) break;
temp.push_back(knownB[i]);
if(ptr<N) {
temp.push_back(ptr);
ptr++;
}
}
rv = use_machine(temp);
ans += rv/2;
if(rv%2==0) {
knownB.push_back(ptr-1);
} else {
knownA.push_back(ptr-1);
}
}
}
return knownA.size()+ans;
}
int smallSol() {
knownA.clear();
knownB.clear();
knownA.push_back(0);
return Phase2(1);
}
int count_mushrooms(int n) {
N = n;
if(n<=320) return smallSol();
else {
Phase1();
return Phase2(302);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |