Submission #310093

#TimeUsernameProblemLanguageResultExecution timeMemory
310093peti1234Counting Mushrooms (IOI20_mushrooms)C++17
0 / 100
3 ms384 KiB
#include <bits/stdc++.h> #include "mushrooms.h" using namespace std; vector<int> a, b, sz; int sa, sb, pos, ert, x, adb; void pb(int x) { sz.push_back(x); } void ap(int x) { a.push_back(x); } void bp(int x) { b.push_back(x); } void cl() { sz.clear(); } /* int use_machine(vector<int>sz) { cout << "kerdes "; for (int i=0; i<sz.size(); i++) cout << sz[i] << " "; cout << "\n"; int x; cin >> x; return x; } */ void add(int a) { if (x%2) bp(a); else ap(a); } void fadd(int a) { if (x%2) ap(a); else bp(a); } int kerd() { return use_machine(sz); } void ek(int a) { pb(0), pb(a); x=kerd(); add(a), cl(); } int count_mushrooms(int n) { a.push_back(0), ert=sqrt(n); if (n<220) { for (int i=1; i<n; i++) ek(i); return a.size(); } for (int i=1; i<=4; i++) ek(i); pos=5; sa=a.size(), sb=b.size(); while(max(sa, sb)<ert) { if (sa>2) { pb(a[0]), pb(pos), pb(a[1]), pb(pos+1), pb(a[2]), pb(pos+2); x=kerd(); add(pos+2); if (x<2) ap(pos), ap(pos+1), pos+=3; else if (x>=4) bp(pos), bp(pos+1), pos+=3; else { if (sb>1) { cl(); pb(b[0]), pb(pos), pb(b[1]), pb(a[0]), pb(pos+1), pb(a[1]), pb(pos+3), pb(a[2]), pb(pos+4); x=kerd()-1; add(pos+4); x/=2; add(pos+3); x/=2; add(pos+1), fadd(pos); pos+=5; } else { cl(); pb(a[0]), pb(pos), pb(a[1]), pb(pos+3); x=kerd(); add(pos+3), x/=2; add(pos), fadd(pos+1); } } } else { pb(b[0]), pb(pos), pb(b[1]), pb(pos+1), pb(b[2]), pb(pos+2); x=kerd(); fadd(pos+2); if (x<2) bp(pos), bp(pos+1), pos+=3; else if (x>=4) ap(pos), ap(pos+1), pos+=3; else { if (sa>1) { cl(); pb(a[0]), pb(pos), pb(a[1]), pb(b[0]), pb(pos+1), pb(b[1]), pb(pos+3), pb(b[2]), pb(pos+4); x=kerd()-1; fadd(pos+4); x/=2; fadd(pos+3); x/=2; fadd(pos+1), add(pos); pos+=5; } else { cl(); pb(b[0]), pb(pos), pb(b[1]), pb(pos+3); x=kerd(); fadd(pos+3), x/=2; fadd(pos), add(pos+1); } } } sa=a.size(), sb=b.size(); } while(pos<n) { cl(); if (sa>=sb) { for (int i=0; i<sa && pos+i<n; i++) { pb(a[i]), pb(pos+i); } x=kerd(); add(sz.back()); pos=1+sz.back(); adb+=(x/2); } else { for (int i=0; i<sb && pos+i<n; i++) { pb(b[i]), pb(pos+i); } x=kerd(); fadd(sz.back()); pos=1+sz.back(); int si=sz.size(); adb+=((si-2)/2-x/2); } sa=a.size(), sb=b.size(); } return sa+adb; } /* int main() { return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...