oj.uz

Submission #318079

# Submission time Handle Problem Language Result Execution time Memory
318079 2020-10-31T12:22:17 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
3.33333 / 100
 20 ms 3180 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 = 1e4;
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);
	}
	
	vector<ii> last; // {val, nxt}
	last.push_back({0, mxp});
	int pt = 0;
	for_(i, 1, MXV+1) {
		if (pt < last.size() and last[pt].second == i) pt++;
		
		if (pt < last.size()) {
			ans[i] = ans[last[pt].first]+1;
		}
		
		for_(f, 0, fac[i].size()) {
			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(f);
			// fac[i].pop_back();
		}
		
		// 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(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:34:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if (pt < last.size() and last[pt].second == i) pt++;
      |       ~~~^~~~~~~~~~~~~
brunhilda.cpp:36:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   if (pt < last.size()) {
      |       ~~~^~~~~~~~~~~~~

Subtask #1
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 876 KB Output isn't correct
2 Incorrect 4 ms 1260 KB Output isn't correct
3 Incorrect 2 ms 876 KB Output isn't correct
4 Incorrect 6 ms 1260 KB Output isn't correct
5 Incorrect 3 ms 1024 KB Output isn't correct
6 Incorrect 2 ms 876 KB Output isn't correct
7 Incorrect 2 ms 876 KB Output isn't correct
8 Incorrect 3 ms 1004 KB Output isn't correct
9 Incorrect 3 ms 1004 KB Output isn't correct
10 Incorrect 4 ms 1132 KB Output isn't correct
11 Incorrect 4 ms 1132 KB Output isn't correct
12 Correct 4 ms 1260 KB Output is correct
13 Correct 8 ms 2156 KB Output is correct
14 Correct 9 ms 2156 KB Output is correct
15 Incorrect 4 ms 1280 KB Output isn't correct
16 Incorrect 5 ms 1268 KB Output isn't correct
17 Incorrect 6 ms 1388 KB Output isn't correct
18 Incorrect 6 ms 1260 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 2 ms 1104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 4 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
5 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 1 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 4 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
9 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 4 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
13 Runtime error 1 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
15 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 1 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 2 ms 1280 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 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 2 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 1 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
8 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 20 ms 3180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 7 ms 2924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 3 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
24 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 1 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 4 ms 1132 KB Execution killed with signal 6 (could be triggered by violating memory limits)
29 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 1 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 1 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 4 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
35 Runtime error 1 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 2 ms 1260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 2 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 3 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
40 Runtime error 4 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
41 Runtime error 3 ms 1260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
42 Runtime error 2 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)