Submission #334268

#	Time	Username	Problem	Language	Result	Execution time	Memory
334268		Fischer	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	41.11 / 100	1108 ms	239340 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;
int head[maxn];
int val[maxn];
int nxt[maxn];
int T = 0;
int cnt[maxn];
int dp[maxn];
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int m, q;
	cin >> m >> q;
	vector<int> p(m);
	memset(head, -1, sizeof head);
	for (int& x : p) {
		cin >> x;
		for (int j=x; j<maxn; j+=x) {
			nxt[T] = head[j];
			head[j] = T;
			val[T] = j - x;
			T++;
		}
	}
	int front = 0;
	cnt[0] = p.size();
	const int mx = 1e9;
	for (int i = 1; i < maxn; ++i) {
		for (int x = head[i]; ~x; x = nxt[x]) {
			cnt[i]++;
			cnt[val[x]]--;
		}
		while (cnt[front] == 0) front++;
		if (front == i) dp[i] = mx;
		else dp[i] = min(mx, dp[front] + 1);
	}
	while (q--) {
		int n;
		cin >> n;
		if (dp[n] > n) cout << "oo\n";
		else cout << dp[n] << '\n';
	}
	return 0;
}

• Subtask 1: 11.11111111111111 / 20
• Subtask 2: 10 / 20
• Subtask 3: 20 / 60