oj.uz

Submission #631343

# Submission time Handle Problem Language Result Execution time Memory
631343 2022-08-18T03:26:47 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
6.66667 / 100
 1000 ms 107436 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){
		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++;
	}

	for (int i = 0; i < Q; i++){
		int a; cin >> a;
		if (dp[a] >= inf) 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:133:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:134:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.66666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 98500 KB Output isn't correct
2 Incorrect 368 ms 98376 KB Output isn't correct
3 Incorrect 383 ms 98380 KB Output isn't correct
4 Correct 413 ms 98324 KB Output is correct
5 Correct 380 ms 98340 KB Output is correct
6 Incorrect 417 ms 98460 KB Output isn't correct
7 Incorrect 380 ms 98340 KB Output isn't correct
8 Incorrect 376 ms 98368 KB Output isn't correct
9 Incorrect 418 ms 98292 KB Output isn't correct
10 Incorrect 372 ms 98328 KB Output isn't correct
11 Incorrect 394 ms 98264 KB Output isn't correct
12 Correct 402 ms 98336 KB Output is correct
13 Correct 379 ms 98340 KB Output is correct
14 Correct 384 ms 98372 KB Output is correct
15 Incorrect 380 ms 98316 KB Output isn't correct
16 Incorrect 400 ms 98208 KB Output isn't correct
17 Incorrect 386 ms 98228 KB Output isn't correct
18 Correct 400 ms 98336 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 99224 KB Time limit exceeded
2 Execution timed out 1093 ms 107436 KB Time limit exceeded
3 Execution timed out 1097 ms 99516 KB Time limit exceeded
4 Incorrect 702 ms 98420 KB Output isn't correct
5 Execution timed out 1094 ms 99740 KB Time limit exceeded
6 Incorrect 494 ms 98356 KB Output isn't correct
7 Execution timed out 1078 ms 99192 KB Time limit exceeded
8 Incorrect 413 ms 98304 KB Output isn't correct
9 Execution timed out 1090 ms 99816 KB Time limit exceeded
10 Execution timed out 1095 ms 99700 KB Time limit exceeded
11 Execution timed out 1096 ms 98964 KB Time limit exceeded
12 Incorrect 512 ms 98464 KB Output isn't correct
13 Execution timed out 1084 ms 98760 KB Time limit exceeded
14 Incorrect 687 ms 98416 KB Output isn't correct
15 Execution timed out 1102 ms 99196 KB Time limit exceeded
16 Execution timed out 1094 ms 107416 KB Time limit exceeded
17 Incorrect 629 ms 98364 KB Output isn't correct
18 Execution timed out 1090 ms 100892 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 99460 KB Time limit exceeded
2 Execution timed out 1090 ms 99208 KB Time limit exceeded
3 Execution timed out 1087 ms 99068 KB Time limit exceeded
4 Incorrect 813 ms 98672 KB Output isn't correct
5 Execution timed out 1092 ms 103048 KB Time limit exceeded
6 Execution timed out 1088 ms 98436 KB Time limit exceeded
7 Execution timed out 1098 ms 100880 KB Time limit exceeded
8 Execution timed out 1091 ms 99388 KB Time limit exceeded
9 Execution timed out 1094 ms 99456 KB Time limit exceeded
10 Incorrect 987 ms 98540 KB Output isn't correct
11 Incorrect 834 ms 98504 KB Output isn't correct
12 Incorrect 999 ms 98524 KB Output isn't correct
13 Execution timed out 1077 ms 98904 KB Time limit exceeded
14 Incorrect 381 ms 98652 KB Output isn't correct
15 Incorrect 833 ms 98544 KB Output isn't correct
16 Incorrect 940 ms 98552 KB Output isn't correct
17 Execution timed out 1091 ms 99188 KB Time limit exceeded
18 Execution timed out 1098 ms 99212 KB Time limit exceeded
19 Execution timed out 1101 ms 98924 KB Time limit exceeded
20 Execution timed out 1101 ms 99180 KB Time limit exceeded
21 Incorrect 405 ms 98628 KB Output isn't correct
22 Execution timed out 1098 ms 100180 KB Time limit exceeded
23 Execution timed out 1097 ms 99760 KB Time limit exceeded
24 Incorrect 511 ms 98584 KB Output isn't correct
25 Incorrect 547 ms 98756 KB Output isn't correct
26 Incorrect 753 ms 98752 KB Output isn't correct
27 Execution timed out 1091 ms 100280 KB Time limit exceeded
28 Incorrect 592 ms 98804 KB Output isn't correct
29 Execution timed out 1073 ms 100160 KB Time limit exceeded
30 Execution timed out 1087 ms 99560 KB Time limit exceeded
31 Execution timed out 1099 ms 98548 KB Time limit exceeded
32 Incorrect 665 ms 98772 KB Output isn't correct
33 Incorrect 680 ms 98748 KB Output isn't correct
34 Execution timed out 1092 ms 100944 KB Time limit exceeded
35 Incorrect 750 ms 98824 KB Output isn't correct
36 Execution timed out 1101 ms 100092 KB Time limit exceeded
37 Execution timed out 1100 ms 102912 KB Time limit exceeded
38 Execution timed out 1099 ms 98416 KB Time limit exceeded
39 Incorrect 673 ms 98776 KB Output isn't correct
40 Execution timed out 1104 ms 98520 KB Time limit exceeded
41 Execution timed out 1088 ms 101956 KB Time limit exceeded
42 Incorrect 563 ms 98748 KB Output isn't correct