제출 #256263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256263		Saboon	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	45.56 / 100	818 ms	262148 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;

int cnt[maxn];
int last[maxn], pre[9*maxn], p[9*maxn];
int Q[maxn], CQ[maxn], tail, head;
int dp[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int m, q;
	cin >> m >> q;
	int sz = 0;
	memset(last, -1, sizeof last);
	for (int i = 0; i < m; i++){
		int x;
		cin >> x;
		p[sz] = x, pre[sz] = last[0], last[0] = sz ++;
	}
	int n = 1000*1000*10;
	int mxm = n+1;
	for (int i = 0; i <= n; i++){
		while (last[i] != -1){
			int idx = last[i];
			if (i > 0)
				cnt[i-p[idx]] ++;
			if (tail == head or Q[head-1] != i)
				Q[head++] = i;
			CQ[head-1] ++;
			if (i+p[idx] <= n){
				if (sz == 9*maxn-1)
					exit(0);
				p[sz] = p[idx], pre[sz] = last[i+p[idx]], last[i+p[idx]] = sz ++;
			}
			last[i] = pre[last[i]];
		}
		while (tail < head and cnt[Q[tail]] == CQ[tail])
			tail ++;
		if (i > 0){
			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: 15.555555555555555 / 20
• Subtask 2: 10 / 20
• Subtask 3: 20 / 60