oj.uz

Submission #631286

# Submission time Handle Problem Language Result Execution time Memory
631286 2022-08-18T02:40:39 Z mousey Brunhilda’s Birthday (BOI13_brunhilda) C++14
8.09524 / 100
 126 ms 79644 KB 
#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++)
	{
		ans[i]=INFINF;
		if(i>=product) continue;
		for(int j = n; j >= 1; j--)
		{
			if(i%a[j])
			{
				ans[i]=min(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 33 ms 78548 KB Output isn't correct
2 Incorrect 94 ms 78528 KB Output isn't correct
3 Incorrect 33 ms 78540 KB Output isn't correct
4 Incorrect 88 ms 78548 KB Output isn't correct
5 Incorrect 104 ms 78508 KB Output isn't correct
6 Incorrect 33 ms 78504 KB Output isn't correct
7 Incorrect 42 ms 78544 KB Output isn't correct
8 Incorrect 38 ms 78572 KB Output isn't correct
9 Incorrect 100 ms 78576 KB Output isn't correct
10 Incorrect 96 ms 78500 KB Output isn't correct
11 Incorrect 108 ms 78696 KB Output isn't correct
12 Correct 97 ms 78464 KB Output is correct
13 Incorrect 86 ms 78568 KB Output isn't correct
14 Incorrect 88 ms 78544 KB Output isn't correct
15 Incorrect 102 ms 78544 KB Output isn't correct
16 Incorrect 107 ms 78492 KB Output isn't correct
17 Incorrect 94 ms 78584 KB Output isn't correct
18 Incorrect 89 ms 78540 KB Output isn't correct

Subtask #2
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 78672 KB Output isn't correct
2 Correct 85 ms 79284 KB Output is correct
3 Correct 80 ms 79112 KB Output is correct
4 Incorrect 85 ms 78492 KB Output isn't correct
5 Correct 80 ms 78940 KB Output is correct
6 Incorrect 88 ms 78484 KB Output isn't correct
7 Incorrect 82 ms 78624 KB Output isn't correct
8 Incorrect 85 ms 78520 KB Output isn't correct
9 Incorrect 82 ms 79052 KB Output isn't correct
10 Correct 84 ms 79108 KB Output is correct
11 Incorrect 84 ms 78804 KB Output isn't correct
12 Incorrect 84 ms 78500 KB Output isn't correct
13 Incorrect 78 ms 78552 KB Output isn't correct
14 Incorrect 85 ms 78600 KB Output isn't correct
15 Incorrect 84 ms 78796 KB Output isn't correct
16 Correct 81 ms 79280 KB Output is correct
17 Incorrect 82 ms 78588 KB Output isn't correct
18 Incorrect 81 ms 79368 KB Output isn't correct

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 79168 KB Output isn't correct
2 Incorrect 90 ms 78992 KB Output isn't correct
3 Incorrect 90 ms 79060 KB Output isn't correct
4 Incorrect 104 ms 78816 KB Output isn't correct
5 Incorrect 98 ms 79552 KB Output isn't correct
6 Incorrect 107 ms 78924 KB Output isn't correct
7 Incorrect 92 ms 79376 KB Output isn't correct
8 Incorrect 93 ms 79028 KB Output isn't correct
9 Incorrect 92 ms 79052 KB Output isn't correct
10 Incorrect 90 ms 78636 KB Output isn't correct
11 Incorrect 91 ms 78656 KB Output isn't correct
12 Incorrect 89 ms 78680 KB Output isn't correct
13 Incorrect 95 ms 79080 KB Output isn't correct
14 Incorrect 114 ms 79160 KB Output isn't correct
15 Incorrect 91 ms 78648 KB Output isn't correct
16 Incorrect 88 ms 78692 KB Output isn't correct
17 Incorrect 83 ms 78880 KB Output isn't correct
18 Incorrect 93 ms 79048 KB Output isn't correct
19 Incorrect 84 ms 78688 KB Output isn't correct
20 Incorrect 88 ms 79120 KB Output isn't correct
21 Incorrect 107 ms 79236 KB Output isn't correct
22 Incorrect 126 ms 79644 KB Output isn't correct
23 Incorrect 122 ms 79272 KB Output isn't correct
24 Incorrect 110 ms 78924 KB Output isn't correct
25 Incorrect 108 ms 78892 KB Output isn't correct
26 Incorrect 108 ms 78816 KB Output isn't correct
27 Incorrect 92 ms 79436 KB Output isn't correct
28 Incorrect 99 ms 78944 KB Output isn't correct
29 Incorrect 109 ms 79588 KB Output isn't correct
30 Incorrect 106 ms 79400 KB Output isn't correct
31 Incorrect 104 ms 78788 KB Output isn't correct
32 Incorrect 106 ms 78896 KB Output isn't correct
33 Incorrect 109 ms 78944 KB Output isn't correct
34 Incorrect 103 ms 79416 KB Output isn't correct
35 Incorrect 95 ms 78936 KB Output isn't correct
36 Incorrect 106 ms 79424 KB Output isn't correct
37 Incorrect 109 ms 79556 KB Output isn't correct
38 Incorrect 111 ms 78868 KB Output isn't correct
39 Incorrect 110 ms 78896 KB Output isn't correct
40 Incorrect 106 ms 78856 KB Output isn't correct
41 Correct 94 ms 79468 KB Output is correct
42 Incorrect 100 ms 78912 KB Output isn't correct