제출 #957379

#제출 시각아이디문제언어결과실행 시간메모리
95737912345678버섯 세기 (IOI20_mushrooms)C++17
80.43 / 100
6 ms956 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; int res, a, b, m, sz; vector<int> x, y; namespace SUB2 { int count_mushrooms(int n) { int res=1; vector<int> qrs; for (int i=1; i<n; i+=2) { if (i==n-1) { if (use_machine(vector<int> {0, i})==0) res++; } else { auto tmp=use_machine(vector<int> {0, i, i+1}); if (tmp==2) res++; else if (tmp==0) res+=2; else { qrs.push_back(i+1); qrs.push_back(i); } } } if (qrs.size()>0) { res+=(use_machine(qrs)+1)/2; } return res; } } int count_mushrooms(int n) { if (n<=282) { return SUB2::count_mushrooms(n); } x.push_back(0); if (use_machine(vector<int> {0, 1})==0) { a=0, b=1, m=0; x.push_back(1); if (use_machine(vector<int> {1, 2})==0) x.push_back(2); else y.push_back(2); } else if (use_machine(vector<int> {1, 2})==0) a=1, b=2, m=1, y.push_back(1), y.push_back(2); else a=0, b=2, m=0, y.push_back(1), x.push_back(2); for (int i=3; i<282; i+=2) { int tmp=use_machine(vector<int> {a, i, b, i+1}); if (m) { if (tmp==3) x.push_back(i), x.push_back(i+1); else if (tmp==2) x.push_back(i), y.push_back(i+1); else if (tmp==1) x.push_back(i+1), y.push_back(i); else y.push_back(i), y.push_back(i+1); } else { if (tmp==3) y.push_back(i), y.push_back(i+1); else if (tmp==2) y.push_back(i), x.push_back(i+1); else if (tmp==1) y.push_back(i+1), x.push_back(i); else x.push_back(i), x.push_back(i+1); } } res=x.size(); if (x.size()>=y.size()) m=0, sz=x.size(); else m=1, sz=y.size(); /* cout<<"debug x : "; for (auto z:x) cout<<z<<' '; cout<<'\n'; cout<<"debug y : "; for (auto z:y) cout<<z<<' '; cout<<'\n'; */ for (int i=283; i<n; i+=sz) { vector<int> qrs; int cnt=0; for (int j=0; j<sz; j++) { if (m) qrs.push_back(y[j]); else qrs.push_back(x[j]); if (i+j<n) qrs.push_back(i+j), cnt++; } int tmp=(use_machine(qrs)+1)/2; if (m) res+=tmp; else res+=cnt-tmp; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...