oj.uz

Submission #631350

# Submission time Handle Problem Language Result Execution time Memory
631350 2022-08-18T03:31:53 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
6.66667 / 100
 1000 ms 107468 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
6.66666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 98444 KB Output isn't correct
2 Incorrect 274 ms 98380 KB Output isn't correct
3 Incorrect 259 ms 98304 KB Output isn't correct
4 Correct 383 ms 98272 KB Output is correct
5 Correct 261 ms 98216 KB Output is correct
6 Incorrect 288 ms 98260 KB Output isn't correct
7 Incorrect 276 ms 98248 KB Output isn't correct
8 Incorrect 271 ms 98280 KB Output isn't correct
9 Incorrect 266 ms 98220 KB Output isn't correct
10 Incorrect 286 ms 98292 KB Output isn't correct
11 Incorrect 289 ms 98256 KB Output isn't correct
12 Correct 427 ms 98280 KB Output is correct
13 Correct 403 ms 98332 KB Output is correct
14 Correct 397 ms 98324 KB Output is correct
15 Incorrect 276 ms 98232 KB Output isn't correct
16 Incorrect 273 ms 98192 KB Output isn't correct
17 Incorrect 297 ms 98276 KB Output isn't correct
18 Correct 401 ms 98328 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 99148 KB Time limit exceeded
2 Execution timed out 1077 ms 107468 KB Time limit exceeded
3 Execution timed out 1103 ms 99608 KB Time limit exceeded
4 Incorrect 703 ms 98428 KB Output isn't correct
5 Execution timed out 1092 ms 99712 KB Time limit exceeded
6 Incorrect 472 ms 98400 KB Output isn't correct
7 Execution timed out 1089 ms 99180 KB Time limit exceeded
8 Incorrect 445 ms 98368 KB Output isn't correct
9 Execution timed out 1095 ms 99992 KB Time limit exceeded
10 Execution timed out 1087 ms 99628 KB Time limit exceeded
11 Execution timed out 1093 ms 98956 KB Time limit exceeded
12 Incorrect 481 ms 98368 KB Output isn't correct
13 Execution timed out 1086 ms 98928 KB Time limit exceeded
14 Incorrect 728 ms 98456 KB Output isn't correct
15 Execution timed out 1101 ms 99268 KB Time limit exceeded
16 Execution timed out 1093 ms 107460 KB Time limit exceeded
17 Incorrect 552 ms 98384 KB Output isn't correct
18 Execution timed out 1101 ms 100648 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 99460 KB Time limit exceeded
2 Execution timed out 1075 ms 99180 KB Time limit exceeded
3 Execution timed out 1096 ms 99092 KB Time limit exceeded
4 Incorrect 733 ms 98676 KB Output isn't correct
5 Execution timed out 1098 ms 103036 KB Time limit exceeded
6 Execution timed out 1092 ms 98420 KB Time limit exceeded
7 Execution timed out 1099 ms 100856 KB Time limit exceeded
8 Execution timed out 1097 ms 99492 KB Time limit exceeded
9 Execution timed out 1107 ms 99472 KB Time limit exceeded
10 Execution timed out 1056 ms 98444 KB Time limit exceeded
11 Incorrect 884 ms 98424 KB Output isn't correct
12 Incorrect 991 ms 98424 KB Output isn't correct
13 Execution timed out 1100 ms 98848 KB Time limit exceeded
14 Incorrect 262 ms 98548 KB Output isn't correct
15 Incorrect 791 ms 98428 KB Output isn't correct
16 Incorrect 923 ms 98548 KB Output isn't correct
17 Execution timed out 1097 ms 99268 KB Time limit exceeded
18 Execution timed out 1100 ms 99200 KB Time limit exceeded
19 Execution timed out 1101 ms 98972 KB Time limit exceeded
20 Execution timed out 1102 ms 99152 KB Time limit exceeded
21 Incorrect 307 ms 98672 KB Output isn't correct
22 Execution timed out 1096 ms 100092 KB Time limit exceeded
23 Execution timed out 1099 ms 99324 KB Time limit exceeded
24 Incorrect 534 ms 98676 KB Output isn't correct
25 Incorrect 540 ms 98684 KB Output isn't correct
26 Incorrect 745 ms 98800 KB Output isn't correct
27 Execution timed out 1102 ms 99924 KB Time limit exceeded
28 Incorrect 608 ms 98768 KB Output isn't correct
29 Execution timed out 1084 ms 100100 KB Time limit exceeded
30 Execution timed out 1095 ms 99440 KB Time limit exceeded
31 Execution timed out 1099 ms 98608 KB Time limit exceeded
32 Incorrect 646 ms 98580 KB Output isn't correct
33 Incorrect 634 ms 98692 KB Output isn't correct
34 Execution timed out 1064 ms 100912 KB Time limit exceeded
35 Incorrect 760 ms 98892 KB Output isn't correct
36 Execution timed out 1094 ms 100164 KB Time limit exceeded
37 Execution timed out 1065 ms 103064 KB Time limit exceeded
38 Execution timed out 1105 ms 98408 KB Time limit exceeded
39 Incorrect 666 ms 98740 KB Output isn't correct
40 Execution timed out 1098 ms 98528 KB Time limit exceeded
41 Execution timed out 1052 ms 102012 KB Time limit exceeded
42 Incorrect 548 ms 98652 KB Output isn't correct