oj.uz

Submission #631298

# Submission time Handle Problem Language Result Execution time Memory
631298 2022-08-18T02:56:57 Z mousey Brunhilda’s Birthday (BOI13_brunhilda) C++14
49.5238 / 100
 900 ms 79624 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()
{
	ll cur=n;
	for(int i = 2; i <= MAXN; i++)
	{
		ans[i]=INFINF;
		if(i>=product) continue;
		if(i<a[n])
		{
			ans[i]=1;
			continue;
		}
		for(int j = n; j >= 1 && j >= n-10; j--)
		{
			if(i%a[j]) ans[i]=min(ans[i], ans[i-i%a[j]]+1);
		}
		for(int j = n-11; 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"; 
}

Compilation message

brunhilda.cpp: In function 'void solve()':
brunhilda.cpp:41:5: warning: unused variable 'cur' [-Wunused-variable]
   41 |  ll cur=n;
      |     ^~~

Subtask #1
15.5555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 78608 KB Output is correct
2 Correct 857 ms 78552 KB Output is correct
3 Correct 43 ms 78516 KB Output is correct
4 Incorrect 772 ms 78584 KB Output isn't correct
5 Correct 787 ms 78552 KB Output is correct
6 Correct 33 ms 78492 KB Output is correct
7 Correct 43 ms 78488 KB Output is correct
8 Correct 77 ms 78500 KB Output is correct
9 Correct 888 ms 78576 KB Output is correct
10 Correct 900 ms 78620 KB Output is correct
11 Correct 883 ms 78576 KB Output is correct
12 Correct 764 ms 78552 KB Output is correct
13 Correct 722 ms 78624 KB Output is correct
14 Incorrect 732 ms 78588 KB Output isn't correct
15 Correct 823 ms 78660 KB Output is correct
16 Correct 815 ms 78576 KB Output is correct
17 Incorrect 814 ms 78664 KB Output isn't correct
18 Incorrect 755 ms 78596 KB Output isn't correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 78600 KB Output is correct
2 Correct 96 ms 79296 KB Output is correct
3 Correct 473 ms 79160 KB Output is correct
4 Incorrect 651 ms 78584 KB Output isn't correct
5 Correct 524 ms 78932 KB Output is correct
6 Incorrect 657 ms 78628 KB Output isn't correct
7 Correct 561 ms 78588 KB Output is correct
8 Incorrect 696 ms 78620 KB Output isn't correct
9 Correct 527 ms 79052 KB Output is correct
10 Correct 475 ms 79232 KB Output is correct
11 Incorrect 580 ms 78968 KB Output isn't correct
12 Incorrect 689 ms 78540 KB Output isn't correct
13 Incorrect 601 ms 78532 KB Output isn't correct
14 Incorrect 657 ms 78728 KB Output isn't correct
15 Correct 565 ms 78880 KB Output is correct
16 Correct 96 ms 79180 KB Output is correct
17 Correct 690 ms 78720 KB Output is correct
18 Incorrect 340 ms 79324 KB Output isn't correct

Subtask #3
22.8571428571 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 79052 KB Output is correct
2 Incorrect 576 ms 78996 KB Output isn't correct
3 Correct 569 ms 79120 KB Output is correct
4 Incorrect 684 ms 78780 KB Output isn't correct
5 Correct 360 ms 79508 KB Output is correct
6 Incorrect 676 ms 78880 KB Output isn't correct
7 Correct 444 ms 79624 KB Output is correct
8 Correct 559 ms 79000 KB Output is correct
9 Correct 562 ms 79104 KB Output is correct
10 Incorrect 666 ms 78720 KB Output isn't correct
11 Incorrect 667 ms 78608 KB Output isn't correct
12 Incorrect 668 ms 78676 KB Output isn't correct
13 Incorrect 604 ms 79032 KB Output isn't correct
14 Incorrect 877 ms 79100 KB Output isn't correct
15 Incorrect 666 ms 78712 KB Output isn't correct
16 Incorrect 666 ms 78640 KB Output isn't correct
17 Incorrect 574 ms 78896 KB Output isn't correct
18 Incorrect 576 ms 79052 KB Output isn't correct
19 Incorrect 571 ms 78772 KB Output isn't correct
20 Correct 565 ms 79252 KB Output is correct
21 Incorrect 855 ms 79156 KB Output isn't correct
22 Correct 551 ms 79564 KB Output is correct
23 Correct 661 ms 79052 KB Output is correct
24 Incorrect 708 ms 78764 KB Output isn't correct
25 Incorrect 741 ms 78872 KB Output isn't correct
26 Incorrect 711 ms 78856 KB Output isn't correct
27 Correct 550 ms 79428 KB Output is correct
28 Incorrect 710 ms 78900 KB Output isn't correct
29 Correct 574 ms 79548 KB Output is correct
30 Correct 643 ms 79240 KB Output is correct
31 Incorrect 682 ms 78780 KB Output isn't correct
32 Incorrect 745 ms 78872 KB Output isn't correct
33 Incorrect 725 ms 78864 KB Output isn't correct
34 Correct 473 ms 79400 KB Output is correct
35 Incorrect 729 ms 78780 KB Output isn't correct
36 Correct 592 ms 79492 KB Output is correct
37 Correct 379 ms 79496 KB Output is correct
38 Incorrect 733 ms 78904 KB Output isn't correct
39 Incorrect 744 ms 78888 KB Output isn't correct
40 Incorrect 711 ms 78832 KB Output isn't correct
41 Correct 219 ms 79420 KB Output is correct
42 Incorrect 784 ms 79000 KB Output isn't correct