제출 #1289737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289737		g4yuhg	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	40 / 100	12 ms	1596 KiB

brunhilda

#include<bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 100005
#define LOG 16
using namespace std;

const ll inf = 1e9;

bool ghuy4g;

ll m, q, p[N], a[N], mxn, mxp;
ll dp[N], nxt[N];

void sub1() {
	for (int i = 1; i <= 1e4; i ++) dp[i] = inf;
	for (int i = 1; i < mxp; i ++) {
		dp[i] = 1;
	}
	for (int i = mxp; i <= mxn; i ++) {
		dp[i] = inf;
		for (int j = 1; j <= m; j ++) {
			ll du = i % p[j];
			if (du == 0) continue;
			dp[i] = min(dp[i], dp[i - du] + 1);
		}
	}
	for (int i = 1; i <= q; i ++) {
		if (dp[a[i]] == inf) {
			cout << "oo" << endl;
		}
		else {
			cout << dp[a[i]] << endl;
		}
	}
}

void sub2(ll cur) {
	ll dem = 0;
	sort(p + 1, p + 1 + m, greater<ll>());
	for (int i = 1; i <= m; i ++) {
		ll j = i;
		while (j <= m && p[j] == p[i]) {
			j ++ ;
		}
		nxt[i] = j;
		i = j - 1;
		dem ++ ;
	}
	ll ans = 0, ok = 1;
	while (true) {
		if (cur == 0) break;
		ans ++ ;
		bool flag = 0;
		ll cnt = 0;
		ll new_cur = cur;
		for (int i = 1; i <= m; i = nxt[i]) {
			if (cur % p[i] == 0) continue;
			cnt ++ ;
			//cur -= cur % p[i];
			flag = 1;
			new_cur = min(new_cur, cur - cur % p[i]);
			if (cnt > 1e8 / dem) break;
		}
		cur = new_cur;
		if (flag == 0) {
			ok = 0;
			break;
		}
		if (cur == 0) break;
	}
	if (ok == 0) {
		cout << "oo" << endl;
	}
	else {
		cout << ans << endl;
	}
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> m >> q;
    for (int i = 1; i <= m; i ++) {
    	cin >> p[i];
    	mxp = max(mxp, p[i]);
    }
    for (int i = 1; i <= q; i ++) {
    	cin >> a[i];
    	mxn = max(mxn, a[i]);
    }
    /*for (int i = 1; i <= q; i ++) {
    		sub2(a[i]);
    	}
    return 0;*/
    if (mxn <= 1e4 && m <= 1e4 && q <= 1e4) {
    	sub1();
    }
    else if (q == 1) {
    	for (int i = 1; i <= q; i ++) {
    		sub2(a[i]);
    	}
    }
    
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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