Submission #334267

#	Time	Username	Problem	Language	Result	Execution time	Memory
334267		Fischer	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	0 / 100	300 ms	262148 KiB

brunhilda

#include <bits/stdc++.h>
#define rep(x, y, z) for (int x = y; x < z; ++x)
#define reo(x, y) for (int x = 0; x < y; ++x)
using namespace std;

const int maxn = 1e7 + 10;
vector<int> f[maxn];
short cnt[maxn];
short dp[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int m, q;
	cin >> m >> q;
	vector<int> p(m);
	for (int& x : p) {
		cin >> x;
		for (int j=x; j<maxn; j+=x) f[j].push_back(j - x);
	}
	int front = 0;
	cnt[0] = p.size();
	for (int i = 1; i < maxn; ++i) {
		cnt[i] += f[i].size();
		for (int v : f[i]) cnt[v]--;
		while (cnt[front] == 0) front++;
		if (front == i) dp[i] = 10000;
		else dp[i] = min(10000, dp[front] + 1);
	}
	while (q--) {
		int n;
		cin >> n;
		if (dp[n] > 10000) cout << "oo\n";
		else cout << dp[n] << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60