Submission #631285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
631285	2022-08-18T02:39:11 Z	mousey	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	8.09524 / 100	122 ms	79676 KB

brunhilda

#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define pdb pair <double, double> 
#define YES cout<<"YES"
#define NO cout<<"NO"
#define endl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll> 
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;

const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const ll N=1e5, MAXN=1e7;
ll n, q;
ll a[N+5];
ll ans[MAXN+5];
ll product=1;

void input()
{
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		product*=a[i];
		if(product>=MAXN) product=MAXN;
	}
}

void solve()
{
	for(int i = 1; i <= MAXN; i++)
	{
		if(i>=product)
		{
			ans[i]=INFINF;
			continue;
		}
		for(int j = n; j >= 1; j--)
		{
			if(i%a[j])
			{
				ans[i]=ans[i-i%a[j]]+1;
				break;
			}
		}
	}
	while(q--)
	{
		ll x;
		cin >> x;
		if(ans[x]==INFINF) cout << "oo";
		else cout << ans[x];
		endl;
	}
}

int main() 
{
//	auto start_time = chrono::high_resolution_clock::now();
//	freopen("test.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
    input();
    solve();
//    auto end_time = chrono::high_resolution_clock::now();
//        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
//        cout << "\n[ " << duration << " ms ]\n"; 
}

Subtask #1

1.11111111111 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	37 ms	78464 KB	Output isn't correct
2	Incorrect	95 ms	78540 KB	Output isn't correct
3	Incorrect	33 ms	78472 KB	Output isn't correct
4	Incorrect	90 ms	78584 KB	Output isn't correct
5	Incorrect	100 ms	78540 KB	Output isn't correct
6	Incorrect	35 ms	78540 KB	Output isn't correct
7	Incorrect	34 ms	78480 KB	Output isn't correct
8	Incorrect	39 ms	78544 KB	Output isn't correct
9	Incorrect	100 ms	78464 KB	Output isn't correct
10	Incorrect	98 ms	78592 KB	Output isn't correct
11	Incorrect	96 ms	78544 KB	Output isn't correct
12	Correct	94 ms	78468 KB	Output is correct
13	Incorrect	88 ms	78540 KB	Output isn't correct
14	Incorrect	110 ms	78520 KB	Output isn't correct
15	Incorrect	97 ms	78540 KB	Output isn't correct
16	Incorrect	97 ms	78540 KB	Output isn't correct
17	Incorrect	97 ms	78568 KB	Output isn't correct
18	Incorrect	91 ms	78556 KB	Output isn't correct

Subtask #2

5.55555555556 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	86 ms	78624 KB	Output isn't correct
2	Correct	86 ms	79200 KB	Output is correct
3	Correct	80 ms	79052 KB	Output is correct
4	Incorrect	84 ms	78516 KB	Output isn't correct
5	Correct	80 ms	78876 KB	Output is correct
6	Incorrect	83 ms	78512 KB	Output isn't correct
7	Incorrect	78 ms	78684 KB	Output isn't correct
8	Incorrect	88 ms	78676 KB	Output isn't correct
9	Incorrect	86 ms	79036 KB	Output isn't correct
10	Correct	80 ms	79028 KB	Output is correct
11	Incorrect	79 ms	78872 KB	Output isn't correct
12	Incorrect	83 ms	78540 KB	Output isn't correct
13	Incorrect	80 ms	78500 KB	Output isn't correct
14	Incorrect	84 ms	78588 KB	Output isn't correct
15	Incorrect	81 ms	78852 KB	Output isn't correct
16	Correct	83 ms	79216 KB	Output is correct
17	Incorrect	83 ms	78528 KB	Output isn't correct
18	Incorrect	93 ms	79352 KB	Output isn't correct

Subtask #3

1.42857142857 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	89 ms	79048 KB	Output isn't correct
2	Incorrect	87 ms	78996 KB	Output isn't correct
3	Incorrect	92 ms	79204 KB	Output isn't correct
4	Incorrect	114 ms	78828 KB	Output isn't correct
5	Incorrect	114 ms	79528 KB	Output isn't correct
6	Incorrect	105 ms	78948 KB	Output isn't correct
7	Incorrect	89 ms	79428 KB	Output isn't correct
8	Incorrect	94 ms	79080 KB	Output isn't correct
9	Incorrect	95 ms	78984 KB	Output isn't correct
10	Incorrect	86 ms	78596 KB	Output isn't correct
11	Incorrect	90 ms	78716 KB	Output isn't correct
12	Incorrect	88 ms	78644 KB	Output isn't correct
13	Incorrect	100 ms	78992 KB	Output isn't correct
14	Incorrect	122 ms	79048 KB	Output isn't correct
15	Incorrect	91 ms	78712 KB	Output isn't correct
16	Incorrect	87 ms	78648 KB	Output isn't correct
17	Incorrect	84 ms	78848 KB	Output isn't correct
18	Incorrect	90 ms	79000 KB	Output isn't correct
19	Incorrect	96 ms	78624 KB	Output isn't correct
20	Incorrect	96 ms	79044 KB	Output isn't correct
21	Incorrect	108 ms	79128 KB	Output isn't correct
22	Incorrect	105 ms	79604 KB	Output isn't correct
23	Incorrect	115 ms	79068 KB	Output isn't correct
24	Incorrect	111 ms	78888 KB	Output isn't correct
25	Incorrect	107 ms	78868 KB	Output isn't correct
26	Incorrect	108 ms	78916 KB	Output isn't correct
27	Incorrect	90 ms	79424 KB	Output isn't correct
28	Incorrect	99 ms	79008 KB	Output isn't correct
29	Incorrect	108 ms	79640 KB	Output isn't correct
30	Incorrect	106 ms	79404 KB	Output isn't correct
31	Incorrect	101 ms	78776 KB	Output isn't correct
32	Incorrect	107 ms	78876 KB	Output isn't correct
33	Incorrect	106 ms	78856 KB	Output isn't correct
34	Incorrect	92 ms	79372 KB	Output isn't correct
35	Incorrect	106 ms	79064 KB	Output isn't correct
36	Incorrect	110 ms	79412 KB	Output isn't correct
37	Incorrect	105 ms	79676 KB	Output isn't correct
38	Incorrect	107 ms	78928 KB	Output isn't correct
39	Incorrect	111 ms	78872 KB	Output isn't correct
40	Incorrect	104 ms	78860 KB	Output isn't correct
41	Correct	92 ms	79364 KB	Output is correct
42	Incorrect	106 ms	78976 KB	Output isn't correct