oj.uz

Submission #318085

# Submission time Handle Problem Language Result Execution time Memory
318085 2020-10-31T12:29:06 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 26 ms 12388 KB 
#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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3436 KB Output is correct
2 Correct 10 ms 5356 KB Output is correct
3 Correct 7 ms 4972 KB Output is correct
4 Correct 5 ms 3308 KB Output is correct
5 Correct 7 ms 4076 KB Output is correct
6 Correct 4 ms 3180 KB Output is correct
7 Correct 8 ms 4972 KB Output is correct
8 Correct 10 ms 5480 KB Output is correct
9 Correct 12 ms 5612 KB Output is correct
10 Correct 13 ms 5740 KB Output is correct
11 Correct 11 ms 5228 KB Output is correct
12 Correct 3 ms 3308 KB Output is correct
13 Correct 18 ms 5996 KB Output is correct
14 Correct 19 ms 5996 KB Output is correct
15 Correct 10 ms 5228 KB Output is correct
16 Correct 10 ms 5356 KB Output is correct
17 Correct 7 ms 3948 KB Output is correct
18 Correct 5 ms 3308 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 6124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 6 ms 6104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 13 ms 8812 KB Execution killed with signal 6 (could be triggered by violating memory limits)
5 Runtime error 7 ms 6380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 13 ms 9964 KB Execution killed with signal 6 (could be triggered by violating memory limits)
7 Runtime error 6 ms 6124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 12 ms 8556 KB Execution killed with signal 6 (could be triggered by violating memory limits)
9 Runtime error 8 ms 6508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 8 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 18 ms 11116 KB Execution killed with signal 6 (could be triggered by violating memory limits)
13 Runtime error 6 ms 5740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 12 ms 8812 KB Execution killed with signal 6 (could be triggered by violating memory limits)
15 Runtime error 8 ms 6508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 6 ms 6124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 24 ms 12012 KB Execution killed with signal 6 (could be triggered by violating memory limits)
18 Runtime error 8 ms 6508 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 6508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 8 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 20 ms 11244 KB Execution killed with signal 6 (could be triggered by violating memory limits)
5 Runtime error 7 ms 6252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 7 ms 6508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 7 ms 6508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 8 ms 6508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 7 ms 6508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 18 ms 11116 KB Execution killed with signal 6 (could be triggered by violating memory limits)
11 Runtime error 16 ms 10220 KB Execution killed with signal 6 (could be triggered by violating memory limits)
12 Runtime error 22 ms 12012 KB Execution killed with signal 6 (could be triggered by violating memory limits)
13 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 20 ms 11616 KB Execution killed with signal 6 (could be triggered by violating memory limits)
15 Runtime error 26 ms 12260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
16 Runtime error 25 ms 12388 KB Execution killed with signal 6 (could be triggered by violating memory limits)
17 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 6 ms 5868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 22 ms 11748 KB Execution killed with signal 6 (could be triggered by violating memory limits)
22 Runtime error 9 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 7 ms 6252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 9 ms 7276 KB Execution killed with signal 6 (could be triggered by violating memory limits)
25 Runtime error 19 ms 11244 KB Execution killed with signal 6 (could be triggered by violating memory limits)
26 Runtime error 20 ms 11244 KB Execution killed with signal 6 (could be triggered by violating memory limits)
27 Runtime error 8 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 5 ms 5356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 7 ms 6124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 14 ms 9324 KB Execution killed with signal 6 (could be triggered by violating memory limits)
33 Runtime error 6 ms 5868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 7 ms 6380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 6 ms 5356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 8 ms 6636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 7 ms 6252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 7 ms 6508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 7 ms 6124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 7 ms 6380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 7 ms 6380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 25 ms 12012 KB Execution killed with signal 6 (could be triggered by violating memory limits)