oj.uz

Submission #631307

# Submission time Handle Problem Language Result Execution time Memory
631307 2022-08-18T03:03:01 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
58.8889 / 100
 1000 ms 160736 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];
vector<int> *divs[maxval];
 
void main_program(){
	int m, Q; cin >> m >> Q;
	vi v(m); cin >> v; sort(all(v));
 
	divs[0] = new vector<int>;
	for (int i = 3; i < m; i++) divs[0]->push_back(v[i]);
 
	for (int i = 0; i < maxval; i++){
		dp[i] = inf;
	}
 
	queue<int> q;
	dp[0] = 0; q.push(0);
 
	int lim = 1;
 
	while (!q.empty()){
		int x = q.front(); q.pop();

		for (int i = 0; i < min(3, m); i++){
			if (x % v[i] == 0){
				while (lim < min(x + v[i], maxval)){
					dp[lim] = dp[x] + 1; q.push(lim);
					lim++;
				}
			}
		}
 
		if (divs[x]){
			for (auto i: *divs[x]){
				while (lim < min(x + i, maxval)){
					dp[lim] = dp[x] + 1; q.push(lim);
					lim++;
				}
				if (x + i < maxval){
					if (!divs[x + i]) divs[x + i] = new vector<int>;
					divs[x + i]->push_back(i);
				}
			}
			delete divs[x];
		}
	}
 
	for (int i = 0; i < Q; i++){
		int x; cin >> x;
		if (dp[x] == inf) cout << "oo\n";
		else cout << dp[x] << "\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:124:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:125:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 39380 KB Output is correct
2 Correct 479 ms 117632 KB Output is correct
3 Correct 30 ms 41428 KB Output is correct
4 Correct 436 ms 117708 KB Output is correct
5 Correct 448 ms 117644 KB Output is correct
6 Correct 26 ms 39452 KB Output is correct
7 Correct 37 ms 41448 KB Output is correct
8 Correct 60 ms 46464 KB Output is correct
9 Correct 630 ms 117676 KB Output is correct
10 Correct 712 ms 117788 KB Output is correct
11 Correct 638 ms 117608 KB Output is correct
12 Correct 389 ms 117712 KB Output is correct
13 Execution timed out 1079 ms 110408 KB Time limit exceeded
14 Execution timed out 1077 ms 110392 KB Time limit exceeded
15 Correct 608 ms 117624 KB Output is correct
16 Correct 533 ms 117740 KB Output is correct
17 Correct 447 ms 117684 KB Output is correct
18 Correct 356 ms 117656 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 122324 KB Output is correct
2 Correct 633 ms 160668 KB Output is correct
3 Execution timed out 1107 ms 102812 KB Time limit exceeded
4 Correct 599 ms 118356 KB Output is correct
5 Execution timed out 1072 ms 123876 KB Time limit exceeded
6 Correct 477 ms 118024 KB Output is correct
7 Correct 578 ms 122288 KB Output is correct
8 Correct 521 ms 117908 KB Output is correct
9 Execution timed out 1058 ms 110604 KB Time limit exceeded
10 Execution timed out 1085 ms 101504 KB Time limit exceeded
11 Execution timed out 1090 ms 101916 KB Time limit exceeded
12 Correct 648 ms 118008 KB Output is correct
13 Correct 428 ms 119956 KB Output is correct
14 Correct 521 ms 118368 KB Output is correct
15 Execution timed out 1099 ms 112780 KB Time limit exceeded
16 Correct 591 ms 160736 KB Output is correct
17 Execution timed out 1100 ms 117732 KB Time limit exceeded
18 Execution timed out 1101 ms 129696 KB Time limit exceeded

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 108024 KB Time limit exceeded
2 Execution timed out 1100 ms 98016 KB Time limit exceeded
3 Execution timed out 1092 ms 92720 KB Time limit exceeded
4 Correct 737 ms 118636 KB Output is correct
5 Correct 639 ms 142812 KB Output is correct
6 Execution timed out 1091 ms 119052 KB Time limit exceeded
7 Execution timed out 1094 ms 136200 KB Time limit exceeded
8 Execution timed out 1091 ms 112364 KB Time limit exceeded
9 Execution timed out 1072 ms 112364 KB Time limit exceeded
10 Correct 749 ms 118568 KB Output is correct
11 Correct 692 ms 118436 KB Output is correct
12 Correct 970 ms 118528 KB Output is correct
13 Execution timed out 1098 ms 107692 KB Time limit exceeded
14 Correct 702 ms 118252 KB Output is correct
15 Execution timed out 1097 ms 118480 KB Time limit exceeded
16 Execution timed out 1101 ms 112128 KB Time limit exceeded
17 Execution timed out 1099 ms 120932 KB Time limit exceeded
18 Execution timed out 1089 ms 100168 KB Time limit exceeded
19 Correct 450 ms 121036 KB Output is correct
20 Execution timed out 1092 ms 105320 KB Time limit exceeded
21 Correct 860 ms 118532 KB Output is correct
22 Execution timed out 1095 ms 104232 KB Time limit exceeded
23 Correct 597 ms 124008 KB Output is correct
24 Correct 407 ms 118468 KB Output is correct
25 Correct 734 ms 118524 KB Output is correct
26 Correct 683 ms 118560 KB Output is correct
27 Execution timed out 1094 ms 105212 KB Time limit exceeded
28 Correct 423 ms 118876 KB Output is correct
29 Execution timed out 1088 ms 112212 KB Time limit exceeded
30 Execution timed out 1097 ms 112992 KB Time limit exceeded
31 Correct 486 ms 119496 KB Output is correct
32 Correct 499 ms 118616 KB Output is correct
33 Correct 367 ms 118860 KB Output is correct
34 Execution timed out 1074 ms 136132 KB Time limit exceeded
35 Correct 438 ms 118820 KB Output is correct
36 Execution timed out 1075 ms 110556 KB Time limit exceeded
37 Correct 622 ms 142828 KB Output is correct
38 Correct 953 ms 119140 KB Output is correct
39 Correct 419 ms 118604 KB Output is correct
40 Correct 878 ms 119480 KB Output is correct
41 Execution timed out 1058 ms 154716 KB Time limit exceeded
42 Execution timed out 1097 ms 118448 KB Time limit exceeded