oj.uz

Submission #318093

# Submission time Handle Problem Language Result Execution time Memory
318093 2020-10-31T12:52:21 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 155 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;
vi qrs[MXV+2];
int qrAns[MXV+2], spf[MXV+2], done[MXV+2];
bool inc[MXV+2];

void pre() {
	memset(spf, -1, sizeof(spf));
	for__(i, 2, MXV+1) if (spf[i] == -1) {
		spf[i] = i;
		for (ll j = i*i; j <= MXV; j += i) spf[j] = i;
	}
}
 
int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	pre();
	
	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;
		inc[p] = true;
		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].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;
		qrs[k].push_back(i);
	}
	
	
	int pt = 0;
	vi fac;
	vector<ii> last;
	last.push_back({0, mxp});
	for_(i, 1, MXV+1) {
		int ans = 0;
		if (pt < last.size() and last[pt].second == i) pt++;
		if (pt < last.size()) ans = last[pt].first+1;
		
		int k = i;
		while (spf[k] != -1) {
			if (inc[spf[k]] and done[spf[k]] != i) {
				done[spf[k]] = i;
				fac.push_back(spf[k]);
			}
			k /= spf[k];
		}
		
		for (int f = fac.size()-1; f >= 0; f--) {
			int nxt = i+fac[f];
			if (ans and last.back().second < nxt) last.push_back({ans, nxt});
			fac.pop_back();
		}
		
		// cout << i << ": " << ans << endl;
		for (int j: qrs[i]) qrAns[j] = ans;
	}
	
	for_(i, 0, q) {
		if (!qrAns[i]) cout << "oo";
		else cout << qrAns[i];
		cout << endl;
	}
	
 
	return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:69: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]
   69 |   if (pt < last.size() and last[pt].second == i) pt++;
      |       ~~~^~~~~~~~~~~~~
brunhilda.cpp:70: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]
   70 |   if (pt < last.size()) ans = last[pt].first+1;
      |       ~~~^~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 146 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 146 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 137 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 142 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 140 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 147 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 139 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 140 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 140 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 139 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 146 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 140 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 138 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 138 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 148 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 144 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 152 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 138 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 140 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 152 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 155 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 140 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 138 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 147 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 139 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 148 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 140 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 144 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 141 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 139 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 138 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 148 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 140 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 147 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 140 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 142 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)