oj.uz

Submission #631295

# Submission time Handle Problem Language Result Execution time Memory
631295 2022-08-18T02:54:07 Z mousey Brunhilda’s Birthday (BOI13_brunhilda) C++14
33.6508 / 100
 489 ms 79576 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-4; j--)
		{
			if(i%a[j]) ans[i]=min(ans[i], ans[i-i%a[j]]+1);
		}
		for(int j = n-5; 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
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 78540 KB Output is correct
2 Incorrect 445 ms 78488 KB Output isn't correct
3 Correct 43 ms 78548 KB Output is correct
4 Incorrect 394 ms 78600 KB Output isn't correct
5 Correct 473 ms 78620 KB Output is correct
6 Correct 33 ms 78540 KB Output is correct
7 Correct 48 ms 78492 KB Output is correct
8 Correct 75 ms 78592 KB Output is correct
9 Correct 489 ms 78552 KB Output is correct
10 Correct 476 ms 78540 KB Output is correct
11 Incorrect 460 ms 78476 KB Output isn't correct
12 Correct 402 ms 78532 KB Output is correct
13 Correct 394 ms 78588 KB Output is correct
14 Incorrect 383 ms 78540 KB Output isn't correct
15 Incorrect 465 ms 78668 KB Output isn't correct
16 Incorrect 423 ms 78492 KB Output isn't correct
17 Incorrect 456 ms 78520 KB Output isn't correct
18 Incorrect 393 ms 78668 KB Output isn't correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 78624 KB Output is correct
2 Correct 72 ms 79224 KB Output is correct
3 Correct 253 ms 79068 KB Output is correct
4 Incorrect 350 ms 78568 KB Output isn't correct
5 Correct 312 ms 78880 KB Output is correct
6 Incorrect 350 ms 78544 KB Output isn't correct
7 Correct 325 ms 78668 KB Output is correct
8 Incorrect 373 ms 78604 KB Output isn't correct
9 Correct 308 ms 79096 KB Output is correct
10 Correct 256 ms 79052 KB Output is correct
11 Incorrect 321 ms 78828 KB Output isn't correct
12 Incorrect 355 ms 78596 KB Output isn't correct
13 Incorrect 331 ms 78568 KB Output isn't correct
14 Incorrect 350 ms 78484 KB Output isn't correct
15 Correct 312 ms 78816 KB Output is correct
16 Correct 78 ms 79180 KB Output is correct
17 Correct 358 ms 78508 KB Output is correct
18 Incorrect 183 ms 79332 KB Output isn't correct

Subtask #3
11.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 324 ms 79040 KB Output isn't correct
2 Incorrect 324 ms 78964 KB Output isn't correct
3 Correct 310 ms 79140 KB Output is correct
4 Incorrect 377 ms 79044 KB Output isn't correct
5 Correct 230 ms 79540 KB Output is correct
6 Incorrect 387 ms 79032 KB Output isn't correct
7 Correct 252 ms 79416 KB Output is correct
8 Incorrect 327 ms 79052 KB Output isn't correct
9 Incorrect 305 ms 78976 KB Output isn't correct
10 Incorrect 355 ms 78552 KB Output isn't correct
11 Incorrect 380 ms 78628 KB Output isn't correct
12 Incorrect 347 ms 78716 KB Output isn't correct
13 Incorrect 335 ms 79084 KB Output isn't correct
14 Incorrect 470 ms 79052 KB Output isn't correct
15 Incorrect 364 ms 78668 KB Output isn't correct
16 Incorrect 357 ms 78600 KB Output isn't correct
17 Incorrect 311 ms 78900 KB Output isn't correct
18 Incorrect 318 ms 79148 KB Output isn't correct
19 Incorrect 325 ms 78780 KB Output isn't correct
20 Correct 322 ms 79148 KB Output is correct
21 Incorrect 449 ms 79168 KB Output isn't correct
22 Incorrect 310 ms 79576 KB Output isn't correct
23 Incorrect 335 ms 78992 KB Output isn't correct
24 Incorrect 375 ms 78776 KB Output isn't correct
25 Incorrect 444 ms 78940 KB Output isn't correct
26 Incorrect 372 ms 78808 KB Output isn't correct
27 Correct 299 ms 79404 KB Output is correct
28 Incorrect 356 ms 79012 KB Output isn't correct
29 Incorrect 340 ms 79496 KB Output isn't correct
30 Incorrect 323 ms 79376 KB Output isn't correct
31 Incorrect 365 ms 78788 KB Output isn't correct
32 Incorrect 370 ms 78848 KB Output isn't correct
33 Incorrect 374 ms 78780 KB Output isn't correct
34 Correct 245 ms 79396 KB Output is correct
35 Incorrect 376 ms 78896 KB Output isn't correct
36 Incorrect 306 ms 79472 KB Output isn't correct
37 Correct 233 ms 79464 KB Output is correct
38 Incorrect 370 ms 78908 KB Output isn't correct
39 Incorrect 386 ms 78796 KB Output isn't correct
40 Incorrect 356 ms 78844 KB Output isn't correct
41 Correct 126 ms 79360 KB Output is correct
42 Incorrect 407 ms 79008 KB Output isn't correct