Submission #713196

#TimeUsernameProblemLanguageResultExecution timeMemory
713196meowwIntercastellar (JOI22_ho_t1)C++14
25 / 100
2072 ms7168 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define endl "\n" int mod=1e9+7; const int N=2e5+5; template<class x> using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>; int n; vector<pair<int,int> > v; void cl(int x) { int idk=log2(x); idk=pow(2,idk); if (idk==x) { v.push_back({x,1}); return; } if (x%2!=0) { v.push_back({1,x}); return; } pair<int,int> gg={1e10,1e10}; int st=x; if (st%2==0) st--; for (int i=st;i>=1;i-=2) { int j=x/i; if (x%i==0 && x%j==0) { if (i%2==0) gg={i,j}; else if (j%2==0) gg={j,i}; else gg={min(i,j),max(i,j)}; break; } } v.push_back(gg); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen(".in", "r", stdin); freopen(".out", "w", stdout); cin>>n; for (int i=0;i<n;i++) { int x; cin>>x; cl(x); } pair<int,int> prfx[n+1]; for (int i=1;i<=n;i++) { prfx[i].first=v[i-1].first+prfx[i-1].first; prfx[i].second=v[i-1].second; } int q; cin>>q; while (q--) { int x; cin>>x; pair<int,int> tmp={x,0}; int i=upper_bound(prfx+1,prfx+(n+1),tmp)-prfx+1; i--; cout<<prfx[i].second<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...