oj.uz

Submission #631338

# Submission time Handle Problem Language Result Execution time Memory
631338 2022-08-18T03:24:35 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
6.66667 / 100
 1000 ms 107524 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 461 ms 98324 KB Output isn't correct
2 Incorrect 452 ms 98340 KB Output isn't correct
3 Incorrect 441 ms 98236 KB Output isn't correct
4 Correct 464 ms 98296 KB Output is correct
5 Correct 449 ms 98316 KB Output is correct
6 Incorrect 454 ms 98364 KB Output isn't correct
7 Incorrect 443 ms 98308 KB Output isn't correct
8 Incorrect 438 ms 98224 KB Output isn't correct
9 Incorrect 529 ms 98232 KB Output isn't correct
10 Incorrect 445 ms 98324 KB Output isn't correct
11 Incorrect 443 ms 98316 KB Output isn't correct
12 Correct 454 ms 98204 KB Output is correct
13 Correct 434 ms 98328 KB Output is correct
14 Correct 428 ms 98460 KB Output is correct
15 Incorrect 451 ms 98424 KB Output isn't correct
16 Incorrect 445 ms 98212 KB Output isn't correct
17 Incorrect 414 ms 98340 KB Output isn't correct
18 Correct 418 ms 98328 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 99244 KB Time limit exceeded
2 Execution timed out 1093 ms 107524 KB Time limit exceeded
3 Execution timed out 1096 ms 99448 KB Time limit exceeded
4 Incorrect 721 ms 98496 KB Output isn't correct
5 Execution timed out 1092 ms 99760 KB Time limit exceeded
6 Incorrect 493 ms 98428 KB Output isn't correct
7 Execution timed out 1095 ms 99244 KB Time limit exceeded
8 Incorrect 476 ms 98292 KB Output isn't correct
9 Execution timed out 1098 ms 99840 KB Time limit exceeded
10 Execution timed out 1092 ms 99576 KB Time limit exceeded
11 Execution timed out 1082 ms 99012 KB Time limit exceeded
12 Incorrect 527 ms 98372 KB Output isn't correct
13 Execution timed out 1086 ms 98784 KB Time limit exceeded
14 Incorrect 739 ms 98424 KB Output isn't correct
15 Execution timed out 1081 ms 99220 KB Time limit exceeded
16 Execution timed out 1094 ms 107464 KB Time limit exceeded
17 Incorrect 618 ms 98364 KB Output isn't correct
18 Execution timed out 1100 ms 100592 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 99596 KB Time limit exceeded
2 Execution timed out 1082 ms 99216 KB Time limit exceeded
3 Execution timed out 1088 ms 99152 KB Time limit exceeded
4 Incorrect 795 ms 98732 KB Output isn't correct
5 Execution timed out 1084 ms 103064 KB Time limit exceeded
6 Execution timed out 1084 ms 98456 KB Time limit exceeded
7 Execution timed out 1099 ms 100936 KB Time limit exceeded
8 Execution timed out 1089 ms 99480 KB Time limit exceeded
9 Execution timed out 1089 ms 99480 KB Time limit exceeded
10 Execution timed out 1028 ms 98516 KB Time limit exceeded
11 Incorrect 874 ms 98496 KB Output isn't correct
12 Execution timed out 1025 ms 98440 KB Time limit exceeded
13 Execution timed out 1097 ms 98684 KB Time limit exceeded
14 Incorrect 414 ms 98592 KB Output isn't correct
15 Incorrect 847 ms 98424 KB Output isn't correct
16 Execution timed out 1004 ms 98552 KB Time limit exceeded
17 Execution timed out 1096 ms 99264 KB Time limit exceeded
18 Execution timed out 1099 ms 99224 KB Time limit exceeded
19 Execution timed out 1086 ms 99116 KB Time limit exceeded
20 Execution timed out 1086 ms 99136 KB Time limit exceeded
21 Incorrect 403 ms 98724 KB Output isn't correct
22 Execution timed out 1101 ms 100052 KB Time limit exceeded
23 Execution timed out 1086 ms 99388 KB Time limit exceeded
24 Incorrect 549 ms 98628 KB Output isn't correct
25 Incorrect 578 ms 98636 KB Output isn't correct
26 Incorrect 769 ms 98580 KB Output isn't correct
27 Execution timed out 1086 ms 99924 KB Time limit exceeded
28 Incorrect 616 ms 98872 KB Output isn't correct
29 Execution timed out 1098 ms 100136 KB Time limit exceeded
30 Execution timed out 1088 ms 99512 KB Time limit exceeded
31 Execution timed out 1098 ms 98584 KB Time limit exceeded
32 Incorrect 702 ms 98652 KB Output isn't correct
33 Incorrect 693 ms 98648 KB Output isn't correct
34 Execution timed out 1057 ms 100872 KB Time limit exceeded
35 Incorrect 768 ms 98812 KB Output isn't correct
36 Execution timed out 1080 ms 100060 KB Time limit exceeded
37 Execution timed out 1097 ms 102936 KB Time limit exceeded
38 Execution timed out 1098 ms 98368 KB Time limit exceeded
39 Incorrect 764 ms 98712 KB Output isn't correct
40 Execution timed out 1089 ms 98464 KB Time limit exceeded
41 Execution timed out 1094 ms 101952 KB Time limit exceeded
42 Incorrect 612 ms 98744 KB Output isn't correct