oj.uz

Submission #631323

# Submission time Handle Problem Language Result Execution time Memory
631323 2022-08-18T03:17:51 Z mousey Brunhilda’s Birthday (BOI13_brunhilda) C++14
10 / 100
 1000 ms 78956 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++)
	{
		if(i>=product) 
		{
			ans[i]=INFINF;
			continue;	
		}
		if(i<a[n])
		{
			ans[i]=1;
			continue;
		}
		ll cnt=0;
		ll curmax=0;
		for(int j = n; j >= 1 && a[j] > curmax; j--)
		{
			if(i%a[j]==0)
			{
				cnt++;
				if(cnt>=2) break;
			}
			curmax=max(curmax, i%a[j]);
		}
		ans[i]=ans[i-curmax]+1;
	}
	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
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 78492 KB Output isn't correct
2 Correct 654 ms 78540 KB Output is correct
3 Incorrect 41 ms 78584 KB Output isn't correct
4 Correct 583 ms 78528 KB Output is correct
5 Correct 354 ms 78528 KB Output is correct
6 Incorrect 40 ms 78476 KB Output isn't correct
7 Incorrect 41 ms 78536 KB Output isn't correct
8 Incorrect 54 ms 78560 KB Output isn't correct
9 Correct 232 ms 78488 KB Output is correct
10 Correct 231 ms 78496 KB Output is correct
11 Correct 259 ms 78480 KB Output is correct
12 Execution timed out 1092 ms 71756 KB Time limit exceeded
13 Execution timed out 1100 ms 35176 KB Time limit exceeded
14 Execution timed out 1078 ms 33156 KB Time limit exceeded
15 Correct 497 ms 78576 KB Output is correct
16 Correct 661 ms 78480 KB Output is correct
17 Incorrect 486 ms 78528 KB Output isn't correct
18 Correct 598 ms 78560 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 7660 KB Time limit exceeded
2 Execution timed out 1044 ms 71608 KB Time limit exceeded
3 Execution timed out 1079 ms 20312 KB Time limit exceeded
4 Execution timed out 1073 ms 4428 KB Time limit exceeded
5 Execution timed out 1081 ms 11056 KB Time limit exceeded
6 Execution timed out 1065 ms 24540 KB Time limit exceeded
7 Execution timed out 1086 ms 7764 KB Time limit exceeded
8 Execution timed out 1084 ms 36872 KB Time limit exceeded
9 Execution timed out 1067 ms 11192 KB Time limit exceeded
10 Execution timed out 1093 ms 20488 KB Time limit exceeded
11 Execution timed out 1062 ms 8608 KB Time limit exceeded
12 Execution timed out 1095 ms 17112 KB Time limit exceeded
13 Execution timed out 1097 ms 5812 KB Time limit exceeded
14 Execution timed out 1095 ms 5184 KB Time limit exceeded
15 Execution timed out 1086 ms 7104 KB Time limit exceeded
16 Execution timed out 1101 ms 71508 KB Time limit exceeded
17 Execution timed out 1095 ms 45992 KB Time limit exceeded
18 Execution timed out 1091 ms 40184 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 8804 KB Time limit exceeded
2 Execution timed out 1092 ms 6216 KB Time limit exceeded
3 Execution timed out 1076 ms 8356 KB Time limit exceeded
4 Execution timed out 1089 ms 4612 KB Time limit exceeded
5 Execution timed out 1078 ms 35932 KB Time limit exceeded
6 Execution timed out 1073 ms 2156 KB Time limit exceeded
7 Execution timed out 1092 ms 23512 KB Time limit exceeded
8 Execution timed out 1078 ms 8932 KB Time limit exceeded
9 Execution timed out 1094 ms 8676 KB Time limit exceeded
10 Execution timed out 1086 ms 2628 KB Time limit exceeded
11 Execution timed out 1089 ms 3608 KB Time limit exceeded
12 Execution timed out 1091 ms 2648 KB Time limit exceeded
13 Execution timed out 1085 ms 7120 KB Time limit exceeded
14 Incorrect 421 ms 78892 KB Output isn't correct
15 Execution timed out 1081 ms 2976 KB Time limit exceeded
16 Execution timed out 1071 ms 2176 KB Time limit exceeded
17 Execution timed out 1077 ms 7100 KB Time limit exceeded
18 Execution timed out 1079 ms 6368 KB Time limit exceeded
19 Execution timed out 1061 ms 6752 KB Time limit exceeded
20 Execution timed out 1076 ms 8432 KB Time limit exceeded
21 Incorrect 430 ms 78956 KB Output isn't correct
22 Execution timed out 1094 ms 12844 KB Time limit exceeded
23 Execution timed out 1081 ms 8488 KB Time limit exceeded
24 Execution timed out 1101 ms 31476 KB Time limit exceeded
25 Execution timed out 1079 ms 10180 KB Time limit exceeded
26 Execution timed out 1087 ms 4412 KB Time limit exceeded
27 Execution timed out 1079 ms 13960 KB Time limit exceeded
28 Execution timed out 1096 ms 60944 KB Time limit exceeded
29 Execution timed out 1082 ms 13096 KB Time limit exceeded
30 Execution timed out 1090 ms 8956 KB Time limit exceeded
31 Execution timed out 1067 ms 3816 KB Time limit exceeded
32 Execution timed out 1086 ms 6904 KB Time limit exceeded
33 Execution timed out 1074 ms 13528 KB Time limit exceeded
34 Execution timed out 1088 ms 23504 KB Time limit exceeded
35 Execution timed out 1063 ms 30400 KB Time limit exceeded
36 Execution timed out 1074 ms 12796 KB Time limit exceeded
37 Execution timed out 1094 ms 35936 KB Time limit exceeded
38 Execution timed out 1077 ms 2004 KB Time limit exceeded
39 Execution timed out 1083 ms 7304 KB Time limit exceeded
40 Execution timed out 1088 ms 2384 KB Time limit exceeded
41 Execution timed out 1081 ms 58728 KB Time limit exceeded
42 Execution timed out 1097 ms 35272 KB Time limit exceeded