Submission #334273

#	Time	Username	Problem	Language	Result	Execution time	Memory
334273		Fischer	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	63.65 / 100	1109 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[10 * maxn];
int nxt[10 * maxn];
int T = 0;
int cnt[maxn];
int dp[maxn];
int p[100010];
 
int main() {
	int m, q;
	scanf("%d%d", &m, &q);
	memset(head, -1, sizeof head);
	for (int i = 0; i < m; ++i) {
		scanf("%d", p+i);
		for (int j=p[i]; j<maxn; j+=p[i]) {
			assert(T < 10 * maxn);
			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 (front < i && cnt[front] == 0) front++;
		if (front == i) dp[i] = mx;
		else dp[i] = min(mx, dp[front] + 1);
	}
	while (q--) {
		int n;
		scanf("%d", &n);
		if (dp[n] > n) puts("oo");
		else printf("%d\n", dp[n]);
	}
	return 0;
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d%d", &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |   scanf("%d", p+i);
      |   ~~~~~^~~~~~~~~~~
brunhilda.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 17.77777777777778 / 20
• Subtask 2: 14.444444444444445 / 20
• Subtask 3: 31.428571428571427 / 60