oj.uz

Submission #631294

# Submission time Handle Problem Language Result Execution time Memory
631294 2022-08-18T02:52:17 Z mousey Brunhilda’s Birthday (BOI13_brunhilda) C++14
27.7778 / 100
 256 ms 79564 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;
		}
		if(i%a[n]) ans[i]=min(ans[i], ans[i-i%a[n]]+1);
		if(n>=2 && i%a[n-1]) ans[i]=min(ans[i], ans[i-i%a[n-1]]+1);
		for(int j = n-2; 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
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 78520 KB Output is correct
2 Incorrect 243 ms 78496 KB Output isn't correct
3 Correct 43 ms 78540 KB Output is correct
4 Incorrect 218 ms 78572 KB Output isn't correct
5 Correct 255 ms 78520 KB Output is correct
6 Correct 36 ms 78540 KB Output is correct
7 Correct 42 ms 78476 KB Output is correct
8 Correct 53 ms 78460 KB Output is correct
9 Correct 256 ms 78544 KB Output is correct
10 Incorrect 255 ms 78472 KB Output isn't correct
11 Incorrect 253 ms 78540 KB Output isn't correct
12 Correct 211 ms 78624 KB Output is correct
13 Correct 214 ms 78548 KB Output is correct
14 Incorrect 219 ms 78604 KB Output isn't correct
15 Incorrect 227 ms 78604 KB Output isn't correct
16 Incorrect 249 ms 78552 KB Output isn't correct
17 Incorrect 230 ms 78644 KB Output isn't correct
18 Incorrect 213 ms 78588 KB Output isn't correct

Subtask #2
7.77777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 78592 KB Output isn't correct
2 Correct 64 ms 79264 KB Output is correct
3 Correct 144 ms 79048 KB Output is correct
4 Incorrect 192 ms 78524 KB Output isn't correct
5 Correct 166 ms 78960 KB Output is correct
6 Incorrect 201 ms 78700 KB Output isn't correct
7 Incorrect 172 ms 78568 KB Output isn't correct
8 Incorrect 204 ms 78600 KB Output isn't correct
9 Correct 162 ms 79056 KB Output is correct
10 Correct 152 ms 79048 KB Output is correct
11 Incorrect 171 ms 78776 KB Output isn't correct
12 Incorrect 196 ms 78568 KB Output isn't correct
13 Incorrect 187 ms 78632 KB Output isn't correct
14 Incorrect 192 ms 78596 KB Output isn't correct
15 Incorrect 168 ms 78856 KB Output isn't correct
16 Correct 62 ms 79300 KB Output is correct
17 Correct 204 ms 78620 KB Output is correct
18 Incorrect 116 ms 79332 KB Output isn't correct

Subtask #3
10.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 79004 KB Output isn't correct
2 Incorrect 187 ms 79040 KB Output isn't correct
3 Correct 174 ms 79052 KB Output is correct
4 Incorrect 215 ms 78796 KB Output isn't correct
5 Correct 134 ms 79472 KB Output is correct
6 Incorrect 232 ms 78924 KB Output isn't correct
7 Correct 146 ms 79448 KB Output is correct
8 Incorrect 187 ms 79044 KB Output isn't correct
9 Incorrect 184 ms 79120 KB Output isn't correct
10 Incorrect 199 ms 78584 KB Output isn't correct
11 Incorrect 206 ms 78592 KB Output isn't correct
12 Incorrect 208 ms 78584 KB Output isn't correct
13 Incorrect 196 ms 78984 KB Output isn't correct
14 Incorrect 252 ms 79048 KB Output isn't correct
15 Incorrect 197 ms 78636 KB Output isn't correct
16 Incorrect 196 ms 78700 KB Output isn't correct
17 Incorrect 174 ms 78908 KB Output isn't correct
18 Incorrect 176 ms 78992 KB Output isn't correct
19 Incorrect 175 ms 78772 KB Output isn't correct
20 Correct 189 ms 79164 KB Output is correct
21 Incorrect 236 ms 79256 KB Output isn't correct
22 Incorrect 195 ms 79560 KB Output isn't correct
23 Incorrect 198 ms 79048 KB Output isn't correct
24 Incorrect 210 ms 78812 KB Output isn't correct
25 Incorrect 220 ms 78924 KB Output isn't correct
26 Incorrect 206 ms 78852 KB Output isn't correct
27 Incorrect 163 ms 79472 KB Output isn't correct
28 Incorrect 207 ms 78972 KB Output isn't correct
29 Incorrect 180 ms 79564 KB Output isn't correct
30 Incorrect 187 ms 79308 KB Output isn't correct
31 Incorrect 197 ms 78856 KB Output isn't correct
32 Incorrect 211 ms 78800 KB Output isn't correct
33 Incorrect 197 ms 78856 KB Output isn't correct
34 Correct 143 ms 79512 KB Output is correct
35 Incorrect 197 ms 78928 KB Output isn't correct
36 Incorrect 182 ms 79476 KB Output isn't correct
37 Correct 133 ms 79448 KB Output is correct
38 Incorrect 212 ms 78912 KB Output isn't correct
39 Incorrect 213 ms 78948 KB Output isn't correct
40 Incorrect 200 ms 78900 KB Output isn't correct
41 Correct 85 ms 79416 KB Output is correct
42 Incorrect 207 ms 78924 KB Output isn't correct