Submission #1247787

#TimeUsernameProblemLanguageResultExecution timeMemory
1247787sean503Brunhilda’s Birthday (BOI13_brunhilda)C++20
100 / 100
308 ms235804 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,1); vector<int> vec(MAX,0); vector<int> go(MAX,1); int biggest = 0; int mul = 1; bool work = true; int small = INT_MAX; int idk = INT_MAX; for(int i = 0; i<n; i++){ int x; cin>>x; small = min(small,x); mul *= x; if(mul > MAX){ work = false; } biggest = max(biggest,x); int temp = x; while(temp < MAX){ if(vec[temp] < x && temp + x >= MAX){ idk = min(idk,temp); } if(vec[temp] < x){ vec[temp] = x; } temp += x; } } for(int i = MAX-1; i>=0; i--){ go[i] = idk; idk = min(idk,i-vec[i]); } for(int i = biggest; i<MAX; i++){ v[i] = v[go[i]]+1; } // vector<int> amt(MAX,0); // int ind = 1; // for(int i = small; i<MAX; i++){ // if(vec[i] != 0){ // if(i >= biggest){ // amt[v[i-vec[i]]+1] ++; // }else{ // amt[v[i-vec[i]]] ++; // } // } // while(i >= biggest && amt[ind] == 0){ // ind++; // } // if(i >= mul && work){ // break; // } // if(i < biggest){ // v[i] = 1; // }else{ // v[i] = ind+1; // } // } v[0] = 0; 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...