oj.uz

Submission #631303

# Submission time Handle Problem Language Result Execution time Memory
631303 2022-08-18T02:59:49 Z mousey Brunhilda’s Birthday (BOI13_brunhilda) C++14
48.7302 / 100
 1000 ms 79556 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-12; j--)
		{
			if(i%a[j]) ans[i]=min(ans[i], ans[i-i%a[j]]+1);
		}
		for(int j = n-13; 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
13.3333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 78488 KB Output is correct
2 Correct 966 ms 78528 KB Output is correct
3 Correct 43 ms 78544 KB Output is correct
4 Incorrect 900 ms 78524 KB Output isn't correct
5 Correct 771 ms 78516 KB Output is correct
6 Correct 34 ms 78552 KB Output is correct
7 Correct 43 ms 78504 KB Output is correct
8 Correct 76 ms 78500 KB Output is correct
9 Correct 857 ms 78560 KB Output is correct
10 Execution timed out 1043 ms 78492 KB Time limit exceeded
11 Execution timed out 1022 ms 78536 KB Time limit exceeded
12 Correct 891 ms 78512 KB Output is correct
13 Correct 864 ms 78580 KB Output is correct
14 Incorrect 850 ms 78692 KB Output isn't correct
15 Correct 980 ms 78532 KB Output is correct
16 Correct 979 ms 78496 KB Output is correct
17 Incorrect 969 ms 78608 KB Output isn't correct
18 Incorrect 900 ms 78624 KB Output isn't correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 78600 KB Output is correct
2 Correct 107 ms 79188 KB Output is correct
3 Correct 562 ms 79020 KB Output is correct
4 Incorrect 781 ms 78676 KB Output isn't correct
5 Correct 622 ms 78980 KB Output is correct
6 Incorrect 782 ms 78516 KB Output isn't correct
7 Correct 656 ms 78576 KB Output is correct
8 Incorrect 827 ms 78500 KB Output isn't correct
9 Correct 621 ms 79068 KB Output is correct
10 Correct 578 ms 79140 KB Output is correct
11 Incorrect 684 ms 78796 KB Output isn't correct
12 Incorrect 798 ms 78620 KB Output isn't correct
13 Incorrect 718 ms 78604 KB Output isn't correct
14 Incorrect 780 ms 78544 KB Output isn't correct
15 Correct 682 ms 78900 KB Output is correct
16 Correct 106 ms 79316 KB Output is correct
17 Correct 811 ms 78620 KB Output is correct
18 Incorrect 384 ms 79248 KB Output isn't correct

Subtask #3
24.2857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 78988 KB Output is correct
2 Incorrect 680 ms 79052 KB Output isn't correct
3 Correct 673 ms 79052 KB Output is correct
4 Incorrect 789 ms 78836 KB Output isn't correct
5 Correct 418 ms 79520 KB Output is correct
6 Incorrect 833 ms 78908 KB Output isn't correct
7 Correct 513 ms 79476 KB Output is correct
8 Correct 658 ms 79012 KB Output is correct
9 Correct 685 ms 79140 KB Output is correct
10 Incorrect 784 ms 78664 KB Output isn't correct
11 Incorrect 791 ms 78660 KB Output isn't correct
12 Incorrect 793 ms 78680 KB Output isn't correct
13 Incorrect 718 ms 79032 KB Output isn't correct
14 Execution timed out 1027 ms 79356 KB Time limit exceeded
15 Incorrect 788 ms 78696 KB Output isn't correct
16 Incorrect 799 ms 78812 KB Output isn't correct
17 Correct 686 ms 78908 KB Output is correct
18 Incorrect 680 ms 79192 KB Output isn't correct
19 Incorrect 690 ms 78680 KB Output isn't correct
20 Correct 664 ms 79212 KB Output is correct
21 Incorrect 963 ms 79196 KB Output isn't correct
22 Correct 622 ms 79504 KB Output is correct
23 Correct 698 ms 79120 KB Output is correct
24 Incorrect 811 ms 78844 KB Output isn't correct
25 Incorrect 830 ms 78924 KB Output isn't correct
26 Incorrect 809 ms 78844 KB Output isn't correct
27 Correct 611 ms 79396 KB Output is correct
28 Incorrect 785 ms 78944 KB Output isn't correct
29 Correct 632 ms 79476 KB Output is correct
30 Correct 680 ms 79324 KB Output is correct
31 Incorrect 735 ms 78852 KB Output isn't correct
32 Incorrect 805 ms 78812 KB Output isn't correct
33 Incorrect 772 ms 78860 KB Output isn't correct
34 Correct 526 ms 79496 KB Output is correct
35 Incorrect 782 ms 78816 KB Output isn't correct
36 Correct 625 ms 79396 KB Output is correct
37 Correct 426 ms 79556 KB Output is correct
38 Incorrect 800 ms 78924 KB Output isn't correct
39 Incorrect 797 ms 78924 KB Output isn't correct
40 Incorrect 751 ms 79004 KB Output isn't correct
41 Correct 222 ms 79392 KB Output is correct
42 Incorrect 841 ms 79084 KB Output isn't correct