Submission #631307

#	Time	Username	Problem	Language	Result	Execution time	Memory
631307		TranGiaHuy1508	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	58.89 / 100	1107 ms	160736 KiB

brunhilda

/*
	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 (stderr)

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.77777777777778 / 20
• Subtask 2: 11.11111111111111 / 20
• Subtask 3: 30 / 60