Submission #334269

#	Time	Username	Problem	Language	Result	Execution time	Memory
334269		Fischer	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	63.65 / 100	1121 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;
int head[maxn];
int val[2 * maxn];
int nxt[2 * maxn];
int T = 0;
int cnt[maxn];
int dp[maxn];
int p[100010];
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int m, q;
	cin >> m >> q;
	memset(head, -1, sizeof head);
	for (int i = 0; i < m; ++i) {
		cin >> p[i];
		for (int j=p[i]; j<maxn; j+=p[i]) {
			nxt[T] = head[j];
			head[j] = T;
			val[T] = j - p[i];
			T++;
		}
	}
	int front = 0;
	cnt[0] = m;
	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: 17.77777777777778 / 20
• Subtask 2: 14.444444444444445 / 20
• Subtask 3: 31.428571428571427 / 60