Submission #36502

#	Time	Username	Problem	Language	Result	Execution time	Memory
36502		cheater2k	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	499 ms	80140 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;

const int MAX = 10000000;
const int inf = 1e9 + 10;

int nprime, nquery;
int maxdiv[MAX + 5];
int dp[MAX + 5];

int main() {
	scanf("%d %d", &nprime, &nquery);
	for (int i = 1; i <= MAX; ++i) dp[i] = inf;
	for (int i = 1; i <= nprime; ++i) {
		int p; scanf("%d", &p);
		for (int j = 0; j <= MAX; j += p) maxdiv[j] = p;
	}
	
	int cur = 0;
	for (int i = 1; i <= MAX; ++i) {
		while(cur < i) {
			if (!maxdiv[cur] || cur + maxdiv[cur] <= i) ++cur;
			else break;
		}
		if (cur == i) continue;
		dp[i] = min(dp[i], dp[cur] + 1);
	}

	while(nquery--) {
		int n; scanf("%d", &n);
		if (dp[n] != inf) printf("%d\n", dp[n]);
		else printf("oo\n");
	}
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:12:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &nprime, &nquery);
                                  ^
brunhilda.cpp:15:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p; scanf("%d", &p);
                         ^
brunhilda.cpp:30:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int n; scanf("%d", &n);
                         ^

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