1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

paiza POH hundred_thousand #_poh

Posted at
  • 基本的に、辞書を作って2分探索だと思う。
  • ただ、この辞書を作る処理が割と重い。もう少し効率的にならないだろうか…。
10.cpp
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
	int M,N;
	scanf("%d%d",&N,&M);
	vector<long long>v(M),q(N),s;
	s.reserve(M*M/2);
	for(int i=0;i<N;i++)scanf("%lld",&q[i]);
	for(int i=0;i<M;i++)scanf("%lld",&v[i]);
	sort(v.begin(),v.end());
	long long z=*max_element(q.begin(),q.end())+999;
	for(int i=0;i<M;i++)for(int j=i;j<M;j++){if(v[i]*v[j]>z)break;s.push_back(v[i]*v[j]);}
	sort(s.begin(),s.end());
	for(auto &x:q)printf("%lld\n",*lower_bound(s.begin(),s.end(),x)-x);
}
10.rb
#!/usr/bin/ruby
N,M,*Q=`dd`.split.map &:to_i
V=Q.pop(M).sort
Z,*S=Q.max+999
M.times{|i|(i...M).all?{|j|V[i]*V[j]<Z&&S<<V[i]*V[j]}}
S.sort!
Q.map{|x|p S.bsearch{|e|e>=x}-x}

複数言語

他の言語は、systemなりexecなりでRubyを呼び出して解答しています…

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?