Submission #256303

#	Time	Username	Problem	Language	Result	Execution time	Memory
256303		Saboon	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	86.03 / 100	1113 ms	213624 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;
	cin >> m >> q;
	int sz = 0;
	memset(last, -1, sizeof last);
	int mxmp = 0;
	for (int i = 0; i < m; i++){
		int x;
		cin >> x;
		if (mark[x])
			continue;
		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 = n+1;
	for (int i = 1; i <= n; 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 ++;
		if (Q[tail] == i){
			dp[i] = -1;
			mxm = i;
			break;
		}
		dp[i] = dp[Q[tail]] + 1;
	}
	while (q --){
		int x;
		cin >> x;
		if (x >= mxm)
			cout << "oo\n";
		else
			cout << dp[x] << '\n';
	}
}

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