oj.uz

Submission #631314

# Submission time Handle Problem Language Result Execution time Memory
631314 2022-08-18T03:10:56 Z mousey Brunhilda’s Birthday (BOI13_brunhilda) C++14
16.9841 / 100
 1000 ms 79152 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 curmax=0;
		for(int j = n; j >= 1 && a[j] > curmax; j--)
		{
			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
15.5555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 78588 KB Output is correct
2 Correct 586 ms 78592 KB Output is correct
3 Correct 38 ms 78520 KB Output is correct
4 Correct 519 ms 78656 KB Output is correct
5 Correct 322 ms 78508 KB Output is correct
6 Correct 37 ms 78556 KB Output is correct
7 Correct 43 ms 78540 KB Output is correct
8 Correct 53 ms 78592 KB Output is correct
9 Correct 199 ms 78548 KB Output is correct
10 Correct 211 ms 78572 KB Output is correct
11 Correct 243 ms 78596 KB Output is correct
12 Execution timed out 1082 ms 78588 KB Time limit exceeded
13 Execution timed out 1081 ms 38104 KB Time limit exceeded
14 Execution timed out 1090 ms 36300 KB Time limit exceeded
15 Correct 432 ms 78540 KB Output is correct
16 Correct 572 ms 78628 KB Output is correct
17 Incorrect 428 ms 78540 KB Output isn't correct
18 Correct 524 ms 78728 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 8016 KB Time limit exceeded
2 Execution timed out 1104 ms 71500 KB Time limit exceeded
3 Execution timed out 1071 ms 20520 KB Time limit exceeded
4 Execution timed out 1091 ms 5032 KB Time limit exceeded
5 Execution timed out 1100 ms 11028 KB Time limit exceeded
6 Execution timed out 1059 ms 28716 KB Time limit exceeded
7 Execution timed out 1091 ms 7852 KB Time limit exceeded
8 Execution timed out 1088 ms 41136 KB Time limit exceeded
9 Execution timed out 1093 ms 11212 KB Time limit exceeded
10 Execution timed out 1096 ms 20524 KB Time limit exceeded
11 Execution timed out 1094 ms 8652 KB Time limit exceeded
12 Execution timed out 1097 ms 18364 KB Time limit exceeded
13 Execution timed out 1074 ms 5948 KB Time limit exceeded
14 Execution timed out 1084 ms 5264 KB Time limit exceeded
15 Execution timed out 1078 ms 7068 KB Time limit exceeded
16 Execution timed out 1091 ms 71756 KB Time limit exceeded
17 Execution timed out 1096 ms 46240 KB Time limit exceeded
18 Execution timed out 1085 ms 40144 KB Time limit exceeded

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 8696 KB Time limit exceeded
2 Execution timed out 1090 ms 6272 KB Time limit exceeded
3 Execution timed out 1090 ms 8408 KB Time limit exceeded
4 Execution timed out 1093 ms 4776 KB Time limit exceeded
5 Execution timed out 1079 ms 35820 KB Time limit exceeded
6 Execution timed out 1081 ms 2052 KB Time limit exceeded
7 Execution timed out 1090 ms 23504 KB Time limit exceeded
8 Execution timed out 1095 ms 8608 KB Time limit exceeded
9 Execution timed out 1085 ms 8596 KB Time limit exceeded
10 Execution timed out 1077 ms 2372 KB Time limit exceeded
11 Execution timed out 1083 ms 3508 KB Time limit exceeded
12 Execution timed out 1075 ms 2648 KB Time limit exceeded
13 Execution timed out 1056 ms 7204 KB Time limit exceeded
14 Correct 400 ms 79152 KB Output is correct
15 Execution timed out 1087 ms 2912 KB Time limit exceeded
16 Execution timed out 1087 ms 2308 KB Time limit exceeded
17 Execution timed out 1085 ms 7068 KB Time limit exceeded
18 Execution timed out 1098 ms 6360 KB Time limit exceeded
19 Execution timed out 1086 ms 6684 KB Time limit exceeded
20 Execution timed out 1084 ms 8416 KB Time limit exceeded
21 Incorrect 423 ms 79100 KB Output isn't correct
22 Execution timed out 1083 ms 12984 KB Time limit exceeded
23 Execution timed out 1097 ms 8564 KB Time limit exceeded
24 Execution timed out 1081 ms 33676 KB Time limit exceeded
25 Execution timed out 1087 ms 11400 KB Time limit exceeded
26 Execution timed out 1089 ms 4536 KB Time limit exceeded
27 Execution timed out 1092 ms 13956 KB Time limit exceeded
28 Execution timed out 1090 ms 61980 KB Time limit exceeded
29 Execution timed out 1089 ms 12988 KB Time limit exceeded
30 Execution timed out 1084 ms 8840 KB Time limit exceeded
31 Execution timed out 1100 ms 3888 KB Time limit exceeded
32 Execution timed out 1087 ms 6728 KB Time limit exceeded
33 Execution timed out 1093 ms 13804 KB Time limit exceeded
34 Execution timed out 1094 ms 23620 KB Time limit exceeded
35 Execution timed out 1088 ms 32424 KB Time limit exceeded
36 Execution timed out 1090 ms 13004 KB Time limit exceeded
37 Execution timed out 1099 ms 35924 KB Time limit exceeded
38 Execution timed out 1082 ms 2252 KB Time limit exceeded
39 Execution timed out 1076 ms 7948 KB Time limit exceeded
40 Execution timed out 1079 ms 2492 KB Time limit exceeded
41 Execution timed out 1039 ms 58816 KB Time limit exceeded
42 Execution timed out 1096 ms 35520 KB Time limit exceeded