oj.uz

Submission #631354

# Submission time Handle Problem Language Result Execution time Memory
631354 2022-08-18T03:35:35 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
35.873 / 100
 1000 ms 90504 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 81316 KB Output is correct
2 Correct 664 ms 81492 KB Output is correct
3 Correct 233 ms 81232 KB Output is correct
4 Correct 610 ms 81484 KB Output is correct
5 Correct 676 ms 81348 KB Output is correct
6 Correct 189 ms 81324 KB Output is correct
7 Correct 200 ms 81244 KB Output is correct
8 Correct 239 ms 81216 KB Output is correct
9 Correct 676 ms 81364 KB Output is correct
10 Correct 721 ms 81400 KB Output is correct
11 Correct 760 ms 81344 KB Output is correct
12 Correct 642 ms 81380 KB Output is correct
13 Correct 671 ms 81464 KB Output is correct
14 Correct 698 ms 81292 KB Output is correct
15 Correct 747 ms 81332 KB Output is correct
16 Correct 744 ms 81344 KB Output is correct
17 Correct 646 ms 81448 KB Output is correct
18 Correct 656 ms 81476 KB Output is correct

Subtask #2
4.44444444444 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 82148 KB Time limit exceeded
2 Execution timed out 1079 ms 90404 KB Time limit exceeded
3 Execution timed out 1098 ms 82576 KB Time limit exceeded
4 Execution timed out 1030 ms 81460 KB Time limit exceeded
5 Execution timed out 1088 ms 82692 KB Time limit exceeded
6 Correct 771 ms 81428 KB Output is correct
7 Execution timed out 1084 ms 82208 KB Time limit exceeded
8 Correct 668 ms 81380 KB Output is correct
9 Execution timed out 1054 ms 82880 KB Time limit exceeded
10 Execution timed out 1090 ms 82512 KB Time limit exceeded
11 Execution timed out 1092 ms 82048 KB Time limit exceeded
12 Correct 883 ms 81404 KB Output is correct
13 Execution timed out 1079 ms 81720 KB Time limit exceeded
14 Execution timed out 1012 ms 81456 KB Time limit exceeded
15 Execution timed out 1070 ms 82264 KB Time limit exceeded
16 Execution timed out 1092 ms 90504 KB Time limit exceeded
17 Correct 875 ms 81392 KB Output is correct
18 Execution timed out 1098 ms 83696 KB Time limit exceeded

Subtask #3
11.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 82436 KB Time limit exceeded
2 Execution timed out 1088 ms 82260 KB Time limit exceeded
3 Execution timed out 1085 ms 82136 KB Time limit exceeded
4 Execution timed out 1057 ms 81588 KB Time limit exceeded
5 Execution timed out 1101 ms 85952 KB Time limit exceeded
6 Execution timed out 1100 ms 81488 KB Time limit exceeded
7 Execution timed out 1084 ms 83972 KB Time limit exceeded
8 Execution timed out 1095 ms 82416 KB Time limit exceeded
9 Execution timed out 1089 ms 82492 KB Time limit exceeded
10 Execution timed out 1104 ms 81452 KB Time limit exceeded
11 Execution timed out 1095 ms 81504 KB Time limit exceeded
12 Execution timed out 1088 ms 81544 KB Time limit exceeded
13 Execution timed out 1090 ms 81768 KB Time limit exceeded
14 Correct 715 ms 81864 KB Output is correct
15 Execution timed out 1076 ms 81468 KB Time limit exceeded
16 Execution timed out 1100 ms 81448 KB Time limit exceeded
17 Execution timed out 1093 ms 82404 KB Time limit exceeded
18 Execution timed out 1097 ms 82108 KB Time limit exceeded
19 Execution timed out 1076 ms 82016 KB Time limit exceeded
20 Execution timed out 1080 ms 82112 KB Time limit exceeded
21 Correct 644 ms 81872 KB Output is correct
22 Execution timed out 1099 ms 83204 KB Time limit exceeded
23 Execution timed out 1076 ms 82396 KB Time limit exceeded
24 Correct 742 ms 81840 KB Output is correct
25 Correct 881 ms 81672 KB Output is correct
26 Execution timed out 1067 ms 81960 KB Time limit exceeded
27 Execution timed out 1099 ms 82988 KB Time limit exceeded
28 Correct 813 ms 81832 KB Output is correct
29 Execution timed out 1088 ms 83244 KB Time limit exceeded
30 Execution timed out 1101 ms 82572 KB Time limit exceeded
31 Execution timed out 1071 ms 81640 KB Time limit exceeded
32 Execution timed out 1029 ms 81708 KB Time limit exceeded
33 Correct 856 ms 81848 KB Output is correct
34 Execution timed out 1103 ms 83904 KB Time limit exceeded
35 Execution timed out 1043 ms 81716 KB Time limit exceeded
36 Execution timed out 1074 ms 83168 KB Time limit exceeded
37 Execution timed out 1097 ms 86000 KB Time limit exceeded
38 Execution timed out 1088 ms 81536 KB Time limit exceeded
39 Correct 953 ms 81848 KB Output is correct
40 Execution timed out 1101 ms 81528 KB Time limit exceeded
41 Execution timed out 1088 ms 84904 KB Time limit exceeded
42 Correct 791 ms 81864 KB Output is correct