Submission #1247732

#TimeUsernameProblemLanguageResultExecution timeMemory
1247732sean503Brunhilda’s Birthday (BOI13_brunhilda)C++20
6.67 / 100
734 ms157516 KiB
#include<iostream> #include<vector> #include<cstdlib> #include<string> #include<algorithm> #include<set> #include<math.h> #include<map> #include<deque> #include<unordered_map> #include<iomanip> #include<queue> #include<array> #include<climits> #include<cstring> #include<unordered_set> #include<cstdint> #include<typeinfo> #include <random> using namespace std; #define int long long const int MAX = 1e7+1; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin>>n>>m; vector<int> v(MAX,0); vector<int> vec(MAX,0); int biggest = 0; int mul = 1; bool work = true; for(int i = 0; i<n; i++){ int x; cin>>x; mul *= x; if(mul > MAX){ work = false; break; } biggest = max(biggest,x); int temp = x; while(temp < MAX){ if(vec[temp] < x){ vec[temp] = x; } temp += x; } } multiset<int> ms; priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq; for(int i = 1; i<=MAX; i++){ while(!pq.empty() && pq.top().first <= i){ ms.erase(ms.find(pq.top().second)); pq.pop(); } if(i < biggest){ v[i] = 1; }else{ v[i] = *ms.begin() + 1; } if(vec[i] != 0){ ms.insert(v[i]); pq.push({vec[i]+i,v[i]}); } } for(int i = 0; i<m; i++){ int x; cin>>x; if(x >= mul && work){ cout<<"oo"<<"\n"; continue; } cout<<v[x]<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...