oj.uz

Submission #631312

# Submission time Handle Problem Language Result Execution time Memory
631312 2022-08-18T03:07:47 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 112 ms 80772 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 = 0; i < maxval; i++){
		dp[i] = inf;
	}
 
	dp[0] = 0;
 
	int x = 0, lim = 1;
 
	while (lim < maxval){
		if (divs[x]){
			for (auto i: *divs[x]){
				while (lim < min(x + i, maxval)){
					dp[lim] = dp[x] + 1;
					lim++;
				}
				if (x + i < maxval){
					if (!divs[x + i]) divs[x + i] = new vector<int>;
					divs[x + i]->push_back(i);
				}
			}
			delete divs[x];
		}
		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:112:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:113:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 79876 KB Execution killed with signal 11
2 Runtime error 89 ms 79948 KB Execution killed with signal 11
3 Runtime error 89 ms 79884 KB Execution killed with signal 11
4 Runtime error 90 ms 79948 KB Execution killed with signal 11
5 Runtime error 92 ms 79868 KB Execution killed with signal 11
6 Runtime error 90 ms 79968 KB Execution killed with signal 11
7 Runtime error 88 ms 79880 KB Execution killed with signal 11
8 Runtime error 89 ms 79952 KB Execution killed with signal 11
9 Runtime error 89 ms 79952 KB Execution killed with signal 11
10 Runtime error 94 ms 79908 KB Execution killed with signal 11
11 Runtime error 88 ms 79928 KB Execution killed with signal 11
12 Runtime error 90 ms 79968 KB Execution killed with signal 11
13 Runtime error 90 ms 79868 KB Execution killed with signal 11
14 Runtime error 91 ms 79936 KB Execution killed with signal 11
15 Runtime error 88 ms 79852 KB Execution killed with signal 11
16 Runtime error 90 ms 79948 KB Execution killed with signal 11
17 Runtime error 89 ms 79952 KB Execution killed with signal 11
18 Runtime error 88 ms 79936 KB Execution killed with signal 11

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 80016 KB Execution killed with signal 11
2 Runtime error 100 ms 80688 KB Execution killed with signal 11
3 Runtime error 96 ms 80548 KB Execution killed with signal 11
4 Runtime error 90 ms 79924 KB Execution killed with signal 11
5 Runtime error 93 ms 80280 KB Execution killed with signal 11
6 Runtime error 91 ms 79900 KB Execution killed with signal 11
7 Runtime error 90 ms 80012 KB Execution killed with signal 11
8 Runtime error 89 ms 79920 KB Execution killed with signal 11
9 Runtime error 96 ms 80540 KB Execution killed with signal 11
10 Runtime error 96 ms 80452 KB Execution killed with signal 11
11 Runtime error 98 ms 80248 KB Execution killed with signal 11
12 Runtime error 90 ms 79932 KB Execution killed with signal 11
13 Runtime error 89 ms 79872 KB Execution killed with signal 11
14 Runtime error 92 ms 79928 KB Execution killed with signal 11
15 Runtime error 93 ms 80288 KB Execution killed with signal 11
16 Runtime error 98 ms 80636 KB Execution killed with signal 11
17 Runtime error 90 ms 79904 KB Execution killed with signal 11
18 Runtime error 112 ms 80724 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 80320 KB Execution killed with signal 11
2 Runtime error 95 ms 80372 KB Execution killed with signal 11
3 Runtime error 95 ms 80276 KB Execution killed with signal 11
4 Runtime error 91 ms 79968 KB Execution killed with signal 11
5 Runtime error 97 ms 80676 KB Execution killed with signal 11
6 Runtime error 90 ms 80016 KB Execution killed with signal 11
7 Runtime error 98 ms 80772 KB Execution killed with signal 11
8 Runtime error 106 ms 80376 KB Execution killed with signal 11
9 Runtime error 99 ms 80460 KB Execution killed with signal 11
10 Runtime error 90 ms 80004 KB Execution killed with signal 11
11 Runtime error 89 ms 79892 KB Execution killed with signal 11
12 Runtime error 91 ms 79916 KB Execution killed with signal 11
13 Runtime error 94 ms 80088 KB Execution killed with signal 11
14 Runtime error 91 ms 79904 KB Execution killed with signal 11
15 Runtime error 93 ms 80008 KB Execution killed with signal 11
16 Runtime error 94 ms 80016 KB Execution killed with signal 11
17 Runtime error 95 ms 80240 KB Execution killed with signal 11
18 Runtime error 99 ms 80456 KB Execution killed with signal 11
19 Runtime error 92 ms 79940 KB Execution killed with signal 11
20 Runtime error 95 ms 80324 KB Execution killed with signal 11
21 Runtime error 90 ms 79924 KB Execution killed with signal 11
22 Runtime error 99 ms 80692 KB Execution killed with signal 11
23 Runtime error 92 ms 80112 KB Execution killed with signal 11
24 Runtime error 89 ms 79912 KB Execution killed with signal 11
25 Runtime error 90 ms 79972 KB Execution killed with signal 11
26 Runtime error 91 ms 79884 KB Execution killed with signal 11
27 Runtime error 100 ms 80716 KB Execution killed with signal 11
28 Runtime error 89 ms 79988 KB Execution killed with signal 11
29 Runtime error 98 ms 80716 KB Execution killed with signal 11
30 Runtime error 98 ms 80460 KB Execution killed with signal 11
31 Runtime error 90 ms 79908 KB Execution killed with signal 11
32 Runtime error 89 ms 79940 KB Execution killed with signal 11
33 Runtime error 94 ms 79872 KB Execution killed with signal 11
34 Runtime error 100 ms 80724 KB Execution killed with signal 11
35 Runtime error 91 ms 79876 KB Execution killed with signal 11
36 Runtime error 95 ms 80684 KB Execution killed with signal 11
37 Runtime error 100 ms 80716 KB Execution killed with signal 11
38 Runtime error 91 ms 80016 KB Execution killed with signal 11
39 Runtime error 89 ms 79956 KB Execution killed with signal 11
40 Runtime error 93 ms 80020 KB Execution killed with signal 11
41 Runtime error 98 ms 80752 KB Execution killed with signal 11
42 Runtime error 96 ms 79868 KB Execution killed with signal 11