Submission #318085

#	Time	Username	Problem	Language	Result	Execution time	Memory
318085		shivensinha4	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	20 / 100	26 ms	12388 KiB

brunhilda

#include "bits/stdc++.h"
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
 
const int MXV = 1e5;
int ans[MXV+2];
vi fac[MXV+2];
 
int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int m, q; cin >> m >> q;
	int mxp = -1;
	for_(i, 0, m)  {
		int p; cin >> p;
		fac[p].push_back(p);
		mxp = max(mxp, p);
	}
	
	deque<ii> last; // {val, nxt}
	last.push_back({0, mxp});
	int pt = 0;
	for_(i, 1, MXV+1) {
		if (last.size() and last.front().second == i) last.pop_front();
		if (last.size()) ans[i] = ans[last.front().first]+1;
		
		for (int f = fac[i].size()-1; f >= 0; f--) {
			int nxt = i+fac[i][f];
			if (ans[i] and last.back().second < nxt) last.push_back({i, nxt});
			if (nxt <= MXV) fac[nxt].push_back(fac[i][f]);
			fac[i].pop_back();
		}
	}
	
	for_(i, 0, q) {
		int k; cin >> k;
		assert(k <= MXV);
		if (!ans[k]) cout << "oo";
		else cout << ans[k];
		cout << endl;
	}
	
 
	return 0;
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:32:6: warning: unused variable 'pt' [-Wunused-variable]
   32 |  int pt = 0;
      |      ^~

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