oj.uz

Submission #631345

# Submission time Handle Problem Language Result Execution time Memory
631345 2022-08-18T03:29:00 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
6.66667 / 100
 1000 ms 107420 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] = min(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 429 ms 98324 KB Output isn't correct
2 Incorrect 389 ms 98212 KB Output isn't correct
3 Incorrect 391 ms 98444 KB Output isn't correct
4 Correct 398 ms 98300 KB Output is correct
5 Correct 396 ms 98316 KB Output is correct
6 Incorrect 431 ms 98444 KB Output isn't correct
7 Incorrect 418 ms 98408 KB Output isn't correct
8 Incorrect 380 ms 98320 KB Output isn't correct
9 Incorrect 406 ms 98276 KB Output isn't correct
10 Incorrect 375 ms 98324 KB Output isn't correct
11 Incorrect 393 ms 98440 KB Output isn't correct
12 Correct 407 ms 98288 KB Output is correct
13 Correct 374 ms 98324 KB Output is correct
14 Correct 403 ms 98300 KB Output is correct
15 Incorrect 380 ms 98312 KB Output isn't correct
16 Incorrect 380 ms 98372 KB Output isn't correct
17 Incorrect 413 ms 98344 KB Output isn't correct
18 Correct 398 ms 98400 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 99344 KB Time limit exceeded
2 Execution timed out 1099 ms 107420 KB Time limit exceeded
3 Execution timed out 1102 ms 99556 KB Time limit exceeded
4 Incorrect 721 ms 98636 KB Output isn't correct
5 Execution timed out 1095 ms 99680 KB Time limit exceeded
6 Incorrect 479 ms 98480 KB Output isn't correct
7 Execution timed out 1098 ms 99232 KB Time limit exceeded
8 Incorrect 444 ms 98436 KB Output isn't correct
9 Execution timed out 1099 ms 100024 KB Time limit exceeded
10 Execution timed out 1093 ms 99524 KB Time limit exceeded
11 Execution timed out 1101 ms 98932 KB Time limit exceeded
12 Incorrect 485 ms 98488 KB Output isn't correct
13 Execution timed out 1104 ms 98844 KB Time limit exceeded
14 Incorrect 737 ms 98420 KB Output isn't correct
15 Execution timed out 1074 ms 99188 KB Time limit exceeded
16 Execution timed out 1090 ms 107368 KB Time limit exceeded
17 Incorrect 591 ms 98336 KB Output isn't correct
18 Execution timed out 1099 ms 100548 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 99452 KB Time limit exceeded
2 Execution timed out 1087 ms 99188 KB Time limit exceeded
3 Execution timed out 1105 ms 99040 KB Time limit exceeded
4 Incorrect 860 ms 98680 KB Output isn't correct
5 Execution timed out 1057 ms 102944 KB Time limit exceeded
6 Execution timed out 1081 ms 98440 KB Time limit exceeded
7 Execution timed out 1078 ms 100888 KB Time limit exceeded
8 Execution timed out 1098 ms 99468 KB Time limit exceeded
9 Execution timed out 1099 ms 99392 KB Time limit exceeded
10 Execution timed out 1012 ms 98488 KB Time limit exceeded
11 Incorrect 854 ms 98456 KB Output isn't correct
12 Incorrect 997 ms 98428 KB Output isn't correct
13 Execution timed out 1096 ms 98740 KB Time limit exceeded
14 Incorrect 396 ms 98624 KB Output isn't correct
15 Incorrect 839 ms 98432 KB Output isn't correct
16 Execution timed out 1032 ms 98476 KB Time limit exceeded
17 Execution timed out 1070 ms 99248 KB Time limit exceeded
18 Execution timed out 1098 ms 99180 KB Time limit exceeded
19 Execution timed out 1095 ms 98928 KB Time limit exceeded
20 Execution timed out 1095 ms 99152 KB Time limit exceeded
21 Incorrect 377 ms 98572 KB Output isn't correct
22 Execution timed out 1085 ms 100092 KB Time limit exceeded
23 Execution timed out 1098 ms 99372 KB Time limit exceeded
24 Incorrect 545 ms 98672 KB Output isn't correct
25 Incorrect 593 ms 98628 KB Output isn't correct
26 Incorrect 742 ms 98640 KB Output isn't correct
27 Execution timed out 1081 ms 99960 KB Time limit exceeded
28 Incorrect 638 ms 98808 KB Output isn't correct
29 Execution timed out 1095 ms 100140 KB Time limit exceeded
30 Execution timed out 1060 ms 99540 KB Time limit exceeded
31 Execution timed out 1099 ms 98572 KB Time limit exceeded
32 Incorrect 710 ms 98704 KB Output isn't correct
33 Incorrect 661 ms 98768 KB Output isn't correct
34 Execution timed out 1101 ms 100976 KB Time limit exceeded
35 Incorrect 753 ms 98816 KB Output isn't correct
36 Execution timed out 1089 ms 100040 KB Time limit exceeded
37 Execution timed out 1091 ms 103040 KB Time limit exceeded
38 Execution timed out 1093 ms 98368 KB Time limit exceeded
39 Incorrect 745 ms 98624 KB Output isn't correct
40 Execution timed out 1086 ms 98484 KB Time limit exceeded
41 Execution timed out 1071 ms 101880 KB Time limit exceeded
42 Incorrect 612 ms 98768 KB Output isn't correct