제출 #408921

#제출 시각아이디문제언어결과실행 시간메모리
408921AmineTrabelsi버섯 세기 (IOI20_mushrooms)C++14
26.37 / 100
16 ms448 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; const int K = 94; int small(int n){ vector<int> m; int ans = 1; for (int i = 1; i < n; i++) ans += (use_machine({0,i}) == 0); return ans; } int count_mushrooms(int n) { if(n <= 200){ return small(n); } bool type = 0; vector<int> known,known_A,known_B; int ind = 3; int ans = 1; // part one bool sec = use_machine({0,1}); bool th = use_machine({0,2}); ans += (sec == 0) + (th == 0); known_A.push_back(0); if(sec == 0)known_A.push_back(1); else known_B.push_back(1); if(th == 0)known_A.push_back(2); else known_B.push_back(2); if(known_A > known_B){ type = 0; known = known_A; }else{ type = 1; known = known_B; } // part two vector<int> m; int i = 0; while(ind < n){ if(i < (int)known.size()){ m.push_back(known[i]); m.push_back(ind); ind++; i++; } if(i == (int)known.size() || ind == n){ int cnt = use_machine(m); int elem = m.size(); if(!(cnt&1)){ known.push_back(m.back()); if(type == 0)ans++; }else if(type)ans++; cnt -= cnt&1; elem-=2; int kn = elem/2; if(type){ ans += cnt/2; }else ans += kn-(cnt/2); m.clear(); i = 0; } } return ans; } /* 21 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 _ = A _A 0 _B 1 _A_A 0 _A_B 1 _B_A 2 _B_B 3 _ = B _A = 1 _B = 0 _B_B 0 _B_A 1 _A_B 2 _A_A 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...