oj.uz

Submission #631353

# Submission time Handle Problem Language Result Execution time Memory
631353 2022-08-18T03:34:40 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
34.7619 / 100
 1000 ms 90608 KB 
/*
	Unknown's C++ Template (v3.2)
*/
 
#include "bits/stdc++.h"
using namespace std;
 
// #define int long long
 
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mid ((l+r)>>1)
#define fi first
#define se second
 
#ifdef LOCAL
	#define debug(x) cout << #x << " = " << x << "\n";
#else
	#define debug(x) ;
#endif
 
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x)
{ out << "(" << x.first << ", " << x.second << ")"; return out; }
 
template <class T>
ostream& operator << (ostream& out, vector<T> x){
	out << "[";
	for (int i=0; i<sz(x); i++) { out << (i ? ", " : "") << x[i]; }
	out << "]"; return out;
}
 
template <class T>
istream& operator >> (istream& in, vector<T> &x){
	for (auto &i: x) in >> i;
	return in;
}
 
const ld PI = acos(-1.0);
const int allmod[3] = {(int)1e9+7, 998244353, (int)1e9+9};
const int mod = allmod[0];
const int maxn = 2e5 + 64;
const int inf = 1e9;
const ld eps = 1e-6;
const int multitest = 0;
 
const int maxval = 1e7 + 10;

int dp[maxval];
bool v[maxval];
int divs[maxval];
vi primes;

void sieve(){
	for (int d = 2; d < maxval; d++){
		if (!divs[d]){
			divs[d] = d;
			primes.pb(d);
		}
		for (int j = 0; j < sz(primes) && primes[j] <= d; j++){
			if (d * primes[j] >= maxval) break;
			divs[d * primes[j]] = primes[j];
		}
	}
}

#define chkmin(a, b) ((a) < (b) ? (a) : (b))

void main_program(){
	int m, Q; cin >> m >> Q;
	vi inp(m); cin >> inp;
	for (int i = 0; i < m; i++){
		int x = inp[i]; v[x] = true;
	}

	sieve();
 
	for (int i = 0; i < maxval; i++){
		dp[i] = inf;
	}
 
	dp[0] = 0;
	for (int i = 1; i < *max_element(all(inp)); i++) dp[i] = 1;

	int x = 0;
	int lim = *max_element(all(inp));
	while (x < maxval && lim < maxval){
		if (x > lim) break;
		int j = x;
		while (j > 1){
			int p = divs[j];
			if (!p) break;
			if (v[p]){
				while (lim < chkmin(maxval, x + p)){
					dp[lim] = dp[x] + 1;
					// if (lim <= 10) cout << lim << " " << dp[lim] << "\n";
					lim++;
				}
			}
			j /= p;
		}
		x++;
	}

	// cout << lim << "\n";

	for (int i = 0; i < Q; i++){
		int a; cin >> a;
		if (a >= lim) cout << "oo\n";
		else cout << dp[a] << "\n";
	}
}
 
void pre_main(){
 
}
 
signed main(){
	#ifdef LOCAL
		auto stime = chrono::high_resolution_clock::now();
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#ifndef ONLINE_JUDGE
		if (fopen(".inp", "r")){
			freopen(".inp", "r", stdin);
			freopen(".out", "w", stdout);
		}
	#endif
	int t = 1; if (multitest) cin >> t;
	pre_main();
	while (t--) main_program();
	#ifdef LOCAL
		auto etime = chrono::high_resolution_clock::now();
		auto duration = chrono::duration_cast<chrono::milliseconds>(etime-stime).count();
		cout << "\n[" << duration << "ms]\n";
	#endif
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:136:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:137:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 615 ms 81440 KB Output isn't correct
2 Correct 662 ms 81348 KB Output is correct
3 Correct 662 ms 81344 KB Output is correct
4 Correct 650 ms 81312 KB Output is correct
5 Correct 636 ms 81344 KB Output is correct
6 Incorrect 606 ms 81356 KB Output isn't correct
7 Correct 653 ms 81348 KB Output is correct
8 Correct 640 ms 81348 KB Output is correct
9 Correct 683 ms 81344 KB Output is correct
10 Correct 652 ms 81608 KB Output is correct
11 Correct 692 ms 81340 KB Output is correct
12 Correct 587 ms 81472 KB Output is correct
13 Correct 668 ms 81384 KB Output is correct
14 Correct 679 ms 81360 KB Output is correct
15 Correct 674 ms 81336 KB Output is correct
16 Correct 674 ms 81352 KB Output is correct
17 Correct 660 ms 81352 KB Output is correct
18 Correct 678 ms 81472 KB Output is correct

Subtask #2
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 82264 KB Time limit exceeded
2 Execution timed out 1079 ms 90492 KB Time limit exceeded
3 Execution timed out 1079 ms 82496 KB Time limit exceeded
4 Execution timed out 1002 ms 81460 KB Time limit exceeded
5 Execution timed out 1097 ms 82700 KB Time limit exceeded
6 Correct 799 ms 81428 KB Output is correct
7 Execution timed out 1089 ms 82280 KB Time limit exceeded
8 Correct 665 ms 81468 KB Output is correct
9 Execution timed out 1093 ms 82892 KB Time limit exceeded
10 Execution timed out 1100 ms 82496 KB Time limit exceeded
11 Execution timed out 1095 ms 81900 KB Time limit exceeded
12 Correct 814 ms 81404 KB Output is correct
13 Execution timed out 1094 ms 81720 KB Time limit exceeded
14 Correct 942 ms 81456 KB Output is correct
15 Execution timed out 1079 ms 82252 KB Time limit exceeded
16 Execution timed out 1089 ms 90608 KB Time limit exceeded
17 Correct 901 ms 81364 KB Output is correct
18 Execution timed out 1084 ms 83672 KB Time limit exceeded

Subtask #3
11.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 82484 KB Time limit exceeded
2 Execution timed out 1100 ms 82240 KB Time limit exceeded
3 Execution timed out 1095 ms 82144 KB Time limit exceeded
4 Execution timed out 1060 ms 81712 KB Time limit exceeded
5 Execution timed out 1098 ms 86076 KB Time limit exceeded
6 Execution timed out 1097 ms 81380 KB Time limit exceeded
7 Execution timed out 1101 ms 83956 KB Time limit exceeded
8 Execution timed out 1097 ms 82492 KB Time limit exceeded
9 Execution timed out 1098 ms 82488 KB Time limit exceeded
10 Execution timed out 1098 ms 81456 KB Time limit exceeded
11 Execution timed out 1100 ms 81424 KB Time limit exceeded
12 Execution timed out 1090 ms 81488 KB Time limit exceeded
13 Execution timed out 1097 ms 81844 KB Time limit exceeded
14 Correct 711 ms 81856 KB Output is correct
15 Execution timed out 1079 ms 81572 KB Time limit exceeded
16 Execution timed out 1097 ms 81456 KB Time limit exceeded
17 Execution timed out 1096 ms 82236 KB Time limit exceeded
18 Execution timed out 1091 ms 82200 KB Time limit exceeded
19 Execution timed out 1065 ms 82040 KB Time limit exceeded
20 Execution timed out 1090 ms 82188 KB Time limit exceeded
21 Correct 751 ms 81864 KB Output is correct
22 Execution timed out 1092 ms 83120 KB Time limit exceeded
23 Execution timed out 1092 ms 82356 KB Time limit exceeded
24 Correct 788 ms 81712 KB Output is correct
25 Correct 961 ms 81672 KB Output is correct
26 Execution timed out 1080 ms 81464 KB Time limit exceeded
27 Execution timed out 1098 ms 82980 KB Time limit exceeded
28 Correct 871 ms 81764 KB Output is correct
29 Execution timed out 1096 ms 83136 KB Time limit exceeded
30 Execution timed out 1080 ms 82488 KB Time limit exceeded
31 Execution timed out 1100 ms 81600 KB Time limit exceeded
32 Correct 994 ms 81692 KB Output is correct
33 Correct 897 ms 81800 KB Output is correct
34 Execution timed out 1098 ms 83988 KB Time limit exceeded
35 Execution timed out 1039 ms 81460 KB Time limit exceeded
36 Execution timed out 1089 ms 83100 KB Time limit exceeded
37 Execution timed out 1092 ms 85956 KB Time limit exceeded
38 Execution timed out 1090 ms 81468 KB Time limit exceeded
39 Execution timed out 1016 ms 81724 KB Time limit exceeded
40 Execution timed out 1092 ms 81672 KB Time limit exceeded
41 Execution timed out 1093 ms 85076 KB Time limit exceeded
42 Correct 850 ms 81776 KB Output is correct