Cod sursa(job #2196492)

Utilizator GarboteialexGarbotei Alex Garboteialex Data 19 aprilie 2018 16:04:54
Problema Cautare binara Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("cocochanel.in");
ofstream fout("cocochanel.out");

#define DM 100000

int n,m;
int c[DM],g[DM];

int bin(int x) {
	int lo = 1, hi = m, mid,fin;
	while(lo <= hi) {
		mid = (lo + hi) / 2;
		if(g[mid] < x) {
			lo = mid + 1;
		} else { 
			fin = mid;
			hi = mid - 1;
		}
	}

	if(g[fin] >= x) {
		return fin;
	}
	return 0;
}

int main() {
	fin >> n >> m;
	for(int i = 1; i <= n; i++) {
		 fin >> c[i];
	}
	for(int i = 1; i <= m; i++) {
		fin >> g[i];
	}

	sort(g + 1, g + 1 + m);

	for(int i = 1; i <= n; i++) {
		int imp = 0;
		for(int j = 1; c[i] * j <= g[m]; j *= 2) {
			if(bin(c[i] * j) && imp < m) {
				imp++;
			}
		}
		fout << imp << '\n';
	}
}