oj.uz

Submission #631281

# Submission time Handle Problem Language Result Execution time Memory
631281 2022-08-18T02:29:11 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
6.66667 / 100
 859 ms 262144 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 ll 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 = 0; 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(m, 5); i++){
		// 	if (x % v[i] == 0){
		// 		for (; lim < min(x + v[i], maxval); lim++){
		// 			dp[lim] = dp[x] + 1; q.push(lim);
		// 		}
		// 	}
		// }

		if (divs[x]){
			for (auto i: *divs[x]){
				for (; lim < min(x + i, maxval); lim++){
					dp[lim] = dp[x] + 1; q.push(lim);
					if (!divs[lim]) divs[lim] = new vector<int>;
					divs[lim]->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:119:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:120:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 435 ms 117736 KB Output isn't correct
2 Incorrect 502 ms 117748 KB Output isn't correct
3 Incorrect 520 ms 117772 KB Output isn't correct
4 Incorrect 451 ms 118028 KB Output isn't correct
5 Incorrect 458 ms 117760 KB Output isn't correct
6 Incorrect 494 ms 117604 KB Output isn't correct
7 Incorrect 444 ms 117672 KB Output isn't correct
8 Incorrect 465 ms 117816 KB Output isn't correct
9 Incorrect 462 ms 117684 KB Output isn't correct
10 Incorrect 460 ms 117632 KB Output isn't correct
11 Incorrect 469 ms 117680 KB Output isn't correct
12 Correct 476 ms 117916 KB Output is correct
13 Correct 558 ms 118348 KB Output is correct
14 Correct 580 ms 118248 KB Output is correct
15 Incorrect 478 ms 117700 KB Output isn't correct
16 Incorrect 523 ms 117872 KB Output isn't correct
17 Incorrect 462 ms 117796 KB Output isn't correct
18 Incorrect 461 ms 118108 KB Output isn't correct

Subtask #2
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 604 ms 177840 KB Output isn't correct
2 Runtime error 239 ms 262144 KB Execution killed with signal 9
3 Runtime error 430 ms 262144 KB Execution killed with signal 9
4 Incorrect 638 ms 124328 KB Output isn't correct
5 Incorrect 641 ms 204616 KB Output isn't correct
6 Incorrect 565 ms 123080 KB Output isn't correct
7 Incorrect 641 ms 177852 KB Output isn't correct
8 Incorrect 548 ms 119716 KB Output isn't correct
9 Correct 760 ms 204792 KB Output is correct
10 Runtime error 456 ms 262144 KB Execution killed with signal 9
11 Incorrect 582 ms 178644 KB Output isn't correct
12 Incorrect 567 ms 121192 KB Output isn't correct
13 Correct 664 ms 151068 KB Output is correct
14 Incorrect 711 ms 124348 KB Output isn't correct
15 Correct 676 ms 171308 KB Output is correct
16 Runtime error 230 ms 262144 KB Execution killed with signal 9
17 Incorrect 471 ms 122300 KB Output isn't correct
18 Runtime error 232 ms 262144 KB Execution killed with signal 9

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 684 ms 184776 KB Output isn't correct
2 Incorrect 697 ms 164840 KB Output isn't correct
3 Incorrect 582 ms 182576 KB Output isn't correct
4 Incorrect 648 ms 124684 KB Output isn't correct
5 Runtime error 243 ms 262144 KB Execution killed with signal 9
6 Incorrect 859 ms 126688 KB Output isn't correct
7 Runtime error 364 ms 262144 KB Execution killed with signal 9
8 Incorrect 671 ms 184736 KB Output isn't correct
9 Incorrect 667 ms 184780 KB Output isn't correct
10 Incorrect 777 ms 124392 KB Output isn't correct
11 Incorrect 650 ms 124504 KB Output isn't correct
12 Incorrect 704 ms 124488 KB Output isn't correct
13 Incorrect 576 ms 170828 KB Output isn't correct
14 Incorrect 475 ms 118396 KB Output isn't correct
15 Incorrect 631 ms 123156 KB Output isn't correct
16 Incorrect 745 ms 123176 KB Output isn't correct
17 Incorrect 683 ms 171464 KB Output isn't correct
18 Incorrect 730 ms 164832 KB Output isn't correct
19 Incorrect 592 ms 164632 KB Output isn't correct
20 Incorrect 553 ms 182528 KB Output isn't correct
21 Incorrect 491 ms 118296 KB Output isn't correct
22 Incorrect 760 ms 218740 KB Output isn't correct
23 Incorrect 675 ms 184844 KB Output isn't correct
24 Incorrect 556 ms 124580 KB Output isn't correct
25 Incorrect 697 ms 121472 KB Output isn't correct
26 Incorrect 675 ms 124616 KB Output isn't correct
27 Incorrect 690 ms 227724 KB Output isn't correct
28 Incorrect 546 ms 131148 KB Output isn't correct
29 Incorrect 759 ms 218680 KB Output isn't correct
30 Incorrect 707 ms 185020 KB Output isn't correct
31 Incorrect 635 ms 137932 KB Output isn't correct
32 Incorrect 638 ms 124012 KB Output isn't correct
33 Incorrect 684 ms 131388 KB Output isn't correct
34 Runtime error 317 ms 262144 KB Execution killed with signal 9
35 Incorrect 553 ms 129680 KB Output isn't correct
36 Incorrect 846 ms 218632 KB Output isn't correct
37 Runtime error 233 ms 262144 KB Execution killed with signal 9
38 Incorrect 787 ms 126684 KB Output isn't correct
39 Incorrect 654 ms 125932 KB Output isn't correct
40 Incorrect 766 ms 131384 KB Output isn't correct
41 Runtime error 240 ms 262144 KB Execution killed with signal 9
42 Incorrect 467 ms 121652 KB Output isn't correct