oj.uz

답안 #318073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
318073 2020-10-31T12:06:12 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 302 ms 262148 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 = 1e7;
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 (int f: fac[i]) {
			int nxt = i+f;
			if (last.back().second < nxt) last.push_back({i, nxt});
			if (nxt <= MXV) fac[nxt].push_back(f);
		}
	}
	
	for_(i, 0, q) {
		int k; cin >> k;
		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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 191 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 203 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 195 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 211 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 204 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 187 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 192 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 202 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 209 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 222 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 209 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 206 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 246 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 207 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 202 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 211 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 212 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 246 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 280 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 217 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 249 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 200 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 234 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 213 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 253 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 285 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 291 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 228 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 203 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 217 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 266 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 255 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 258 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 268 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 279 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 286 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 231 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 261 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 253 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 249 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 271 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 270 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 234 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 234 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 248 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 284 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 228 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 263 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 264 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 251 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 284 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 199 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 282 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 233 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 279 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 253 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 215 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 228 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 228 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 302 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 208 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 280 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 257 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 221 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 233 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 213 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 254 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 220 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 288 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 260 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 259 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 225 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 245 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 249 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)