제출 #408905

#제출 시각아이디문제언어결과실행 시간메모리
408905AmineTrabelsi버섯 세기 (IOI20_mushrooms)C++14
0 / 100
3 ms200 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; const int K = 100; 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; int ind = 1; int ans = 1; // part one bool sec = use_machine({0,1}); bool th = use_machine({0,2}); ans += (sec == 0) + (th == 0); if(sec == th){ if(sec == 0){ known.push_back(0); known.push_back(1); known.push_back(2); }else{ type = 1; known.push_back(1); known.push_back(2); } }else{ if(sec == 0){ known.push_back(0); known.push_back(1); }else{ known.push_back(0); known.push_back(2); } } // 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...