Submission #256315

#	Time	Username	Problem	Language	Result	Execution time	Memory
256315		Saboon	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	91.43 / 100	1109 ms	214520 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
 
const int maxn = 1e7 + 10;
 
short cnt[maxn];
int last[maxn], pre[maxn], p[maxn];
int Q[maxn], tail, head;
int dp[maxn];
bitset<maxn> mark;
 
int main(){
	ios_base::sync_with_stdio(false);
	int m, q;
	scanf("%d%d", &m, &q);
	int sz = 0;
	memset(last, -1, sizeof last);
	int mxmp = 0;
	int tof = 1;
	while (m --){
		int x;
		scanf("%d", &x);
		if (mark[x])
			continue;
		if (tof <= maxn)
			tof *= x;
		mxmp = max(mxmp, x);
		mark[x] = 1;
		cnt[0] ++;
		p[sz] = x, pre[sz] = last[x], last[x] = sz ++;
	}
	Q[head++] = 0;
	int n = 1000*1000*10;
	int mxm = min(n+1,tof);
	for (int i = 1; i < mxm; i++){
		while (last[i] != -1){
			int idx = last[i];
			cnt[i-p[idx]] --;
			if (tail == head or Q[head-1] != i)
				Q[head++] = i;
			cnt[i] ++;
			if (i+p[idx] <= n){
				p[sz] = p[idx], pre[sz] = last[i+p[idx]], last[i+p[idx]] = sz ++;
				if (sz == maxn)
					sz = 0;
			}
			last[i] = pre[last[i]];
		}
		if (tail == 0){
			if (i >= mxmp)
				tail ++;
			else
				cnt[0] = 1;
		}
		while (tail < head and cnt[Q[tail]] == 0)
			tail ++;
		dp[i] = dp[Q[tail]] + 1;
	}
	while (q --){
		int x;
		scanf("%d", &x);
		if (x >= mxm)
			printf("oo\n");
		else
			printf("%d\n", dp[x]);
	}
}

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]
  scanf("%d%d", &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
brunhilda.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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