oj.uz

Submission #631310

# Submission time Handle Problem Language Result Execution time Memory
631310 2022-08-18T03:05:16 Z TranGiaHuy1508 Brunhilda’s Birthday (BOI13_brunhilda) C++17
60.3175 / 100
 1000 ms 160728 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 = 2; 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(2, 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 28 ms 39392 KB Output is correct
2 Correct 391 ms 117608 KB Output is correct
3 Correct 26 ms 41484 KB Output is correct
4 Correct 289 ms 117700 KB Output is correct
5 Correct 366 ms 117712 KB Output is correct
6 Correct 21 ms 39432 KB Output is correct
7 Correct 35 ms 41440 KB Output is correct
8 Correct 68 ms 46420 KB Output is correct
9 Correct 621 ms 117616 KB Output is correct
10 Correct 777 ms 117656 KB Output is correct
11 Correct 614 ms 117616 KB Output is correct
12 Correct 286 ms 117676 KB Output is correct
13 Execution timed out 1091 ms 113824 KB Time limit exceeded
14 Execution timed out 1090 ms 115212 KB Time limit exceeded
15 Correct 431 ms 117644 KB Output is correct
16 Correct 382 ms 117660 KB Output is correct
17 Correct 365 ms 117652 KB Output is correct
18 Correct 347 ms 117736 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 122268 KB Output is correct
2 Correct 554 ms 160728 KB Output is correct
3 Execution timed out 1102 ms 101968 KB Time limit exceeded
4 Correct 459 ms 118384 KB Output is correct
5 Execution timed out 1084 ms 119912 KB Time limit exceeded
6 Correct 374 ms 118196 KB Output is correct
7 Correct 457 ms 122224 KB Output is correct
8 Correct 513 ms 117976 KB Output is correct
9 Execution timed out 1083 ms 107888 KB Time limit exceeded
10 Execution timed out 1088 ms 96068 KB Time limit exceeded
11 Execution timed out 1081 ms 94780 KB Time limit exceeded
12 Correct 663 ms 118040 KB Output is correct
13 Correct 369 ms 119900 KB Output is correct
14 Correct 459 ms 118324 KB Output is correct
15 Execution timed out 1099 ms 102308 KB Time limit exceeded
16 Correct 528 ms 160724 KB Output is correct
17 Execution timed out 1081 ms 118272 KB Time limit exceeded
18 Execution timed out 1105 ms 135448 KB Time limit exceeded

Subtask #3
31.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 108444 KB Time limit exceeded
2 Execution timed out 1092 ms 102316 KB Time limit exceeded
3 Execution timed out 1096 ms 99176 KB Time limit exceeded
4 Correct 721 ms 118600 KB Output is correct
5 Correct 596 ms 142820 KB Output is correct
6 Execution timed out 1028 ms 119012 KB Time limit exceeded
7 Execution timed out 1091 ms 129800 KB Time limit exceeded
8 Execution timed out 1094 ms 111452 KB Time limit exceeded
9 Execution timed out 1088 ms 108144 KB Time limit exceeded
10 Correct 764 ms 118504 KB Output is correct
11 Correct 618 ms 118416 KB Output is correct
12 Correct 976 ms 118544 KB Output is correct
13 Execution timed out 1093 ms 110988 KB Time limit exceeded
14 Correct 755 ms 118204 KB Output is correct
15 Execution timed out 1095 ms 118548 KB Time limit exceeded
16 Execution timed out 1100 ms 114056 KB Time limit exceeded
17 Execution timed out 1066 ms 119712 KB Time limit exceeded
18 Execution timed out 1093 ms 94304 KB Time limit exceeded
19 Correct 379 ms 121052 KB Output is correct
20 Execution timed out 1100 ms 105108 KB Time limit exceeded
21 Correct 859 ms 118348 KB Output is correct
22 Execution timed out 1100 ms 110396 KB Time limit exceeded
23 Correct 547 ms 123988 KB Output is correct
24 Correct 329 ms 118540 KB Output is correct
25 Correct 710 ms 118604 KB Output is correct
26 Correct 650 ms 118592 KB Output is correct
27 Execution timed out 1096 ms 103884 KB Time limit exceeded
28 Correct 347 ms 118896 KB Output is correct
29 Execution timed out 1096 ms 113536 KB Time limit exceeded
30 Execution timed out 1100 ms 110780 KB Time limit exceeded
31 Correct 440 ms 119648 KB Output is correct
32 Correct 459 ms 118660 KB Output is correct
33 Correct 302 ms 118908 KB Output is correct
34 Execution timed out 1087 ms 136300 KB Time limit exceeded
35 Correct 383 ms 118944 KB Output is correct
36 Execution timed out 1094 ms 110464 KB Time limit exceeded
37 Correct 581 ms 143008 KB Output is correct
38 Correct 972 ms 119256 KB Output is correct
39 Correct 364 ms 118648 KB Output is correct
40 Correct 848 ms 119400 KB Output is correct
41 Correct 987 ms 154808 KB Output is correct
42 Execution timed out 1099 ms 116832 KB Time limit exceeded