Submission #31866

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
31866	2017-09-11T08:08:19 Z	huynd2001	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	62.8571 / 100	656 ms	80532 KB

brunhilda

/*huypheu
2 2
2 3
5
6
*/
#include <bits/stdc++.h>
#define oo (INT_MAX/2)
using namespace std;

int pri[10000005],dp[10000005];
int a[100005];

int main()
{
	int n,q;
	cin >> n >> q;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	int maxo=10000007;
	for(int i=1;i<=maxo;i++) dp[i]=oo;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=(maxo/a[i]);j++)
		{
			pri[a[i]*j]=a[i];
		}
	}
	dp[0]=0;
	int curl=0,curr=0+pri[0]-1;
	for(int i=1;i<=maxo;i++)
	{
		while(i>curr)
		{
			curl++;
			curr=curl+pri[curl]-1;
		}
		dp[i]=min(dp[curl]+1,dp[i]);
	}
	// for(int i=1;i<=10;i++)
	// {
	// 	cout << dp[i] << " ";	
	// }
	// cout << endl;
	for(int i=1;i<=q;i++)
	{
		int b;
		cin >> b;
		if(dp[b]>=maxo) cout << "oo\n"; else cout << dp[b] << "\n";
	}
	return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:40:30: warning: iteration 10000004u invokes undefined behavior [-Waggressive-loop-optimizations]
   dp[i]=min(dp[curl]+1,dp[i]);
                              ^
brunhilda.cpp:33:15: note: containing loop
  for(int i=1;i<=maxo;i++)
               ^
brunhilda.cpp:23:35: warning: iteration 10000004u invokes undefined behavior [-Waggressive-loop-optimizations]
  for(int i=1;i<=maxo;i++) dp[i]=oo;
                                   ^
brunhilda.cpp:23:15: note: containing loop
  for(int i=1;i<=maxo;i++) dp[i]=oo;
               ^

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	80532 KB	Output is correct
2	Correct	103 ms	80532 KB	Output is correct
3	Correct	83 ms	80532 KB	Output is correct
4	Correct	109 ms	80532 KB	Output is correct
5	Correct	126 ms	80532 KB	Output is correct
6	Correct	66 ms	80532 KB	Output is correct
7	Correct	83 ms	80532 KB	Output is correct
8	Correct	83 ms	80532 KB	Output is correct
9	Correct	106 ms	80532 KB	Output is correct
10	Correct	146 ms	80532 KB	Output is correct
11	Correct	133 ms	80532 KB	Output is correct
12	Correct	53 ms	80532 KB	Output is correct
13	Correct	316 ms	80532 KB	Output is correct
14	Correct	366 ms	80532 KB	Output is correct
15	Correct	119 ms	80532 KB	Output is correct
16	Correct	89 ms	80532 KB	Output is correct
17	Correct	163 ms	80532 KB	Output is correct
18	Correct	119 ms	80532 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	80532 KB	Output is correct
2	Correct	139 ms	80532 KB	Output is correct
3	Correct	406 ms	80532 KB	Output is correct
4	Correct	119 ms	80532 KB	Output is correct
5	Correct	286 ms	80532 KB	Output is correct
6	Correct	79 ms	80532 KB	Output is correct
7	Correct	89 ms	80532 KB	Output is correct
8	Correct	133 ms	80532 KB	Output is correct
9	Correct	333 ms	80532 KB	Output is correct
10	Correct	416 ms	80532 KB	Output is correct
11	Correct	386 ms	80532 KB	Output is correct
12	Correct	166 ms	80532 KB	Output is correct
13	Correct	63 ms	80532 KB	Output is correct
14	Correct	123 ms	80532 KB	Output is correct
15	Correct	303 ms	80532 KB	Output is correct
16	Correct	123 ms	80532 KB	Output is correct
17	Correct	306 ms	80532 KB	Output is correct
18	Correct	333 ms	80532 KB	Output is correct

Subtask #3

22.8571428571 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	473 ms	80532 KB	Output is correct
2	Runtime error	649 ms	80532 KB	Execution timed out (wall clock limit exceeded)
3	Runtime error	609 ms	80532 KB	Execution timed out (wall clock limit exceeded)
4	Runtime error	403 ms	80532 KB	Execution timed out (wall clock limit exceeded)
5	Runtime error	353 ms	80532 KB	Execution timed out (wall clock limit exceeded)
6	Runtime error	546 ms	80532 KB	Execution timed out (wall clock limit exceeded)
7	Runtime error	436 ms	80532 KB	Execution timed out (wall clock limit exceeded)
8	Correct	489 ms	80532 KB	Output is correct
9	Correct	416 ms	80532 KB	Output is correct
10	Correct	276 ms	80532 KB	Output is correct
11	Correct	313 ms	80532 KB	Output is correct
12	Correct	363 ms	80532 KB	Output is correct
13	Runtime error	553 ms	80532 KB	Execution timed out (wall clock limit exceeded)
14	Runtime error	336 ms	80532 KB	Execution timed out (wall clock limit exceeded)
15	Correct	413 ms	80532 KB	Output is correct
16	Correct	556 ms	80532 KB	Output is correct
17	Correct	319 ms	80532 KB	Output is correct
18	Correct	459 ms	80532 KB	Output is correct
19	Correct	149 ms	80532 KB	Output is correct
20	Runtime error	636 ms	80532 KB	Execution timed out (wall clock limit exceeded)
21	Runtime error	379 ms	80532 KB	Execution timed out (wall clock limit exceeded)
22	Runtime error	593 ms	80532 KB	Execution timed out (wall clock limit exceeded)
23	Runtime error	319 ms	80532 KB	Execution timed out (wall clock limit exceeded)
24	Runtime error	246 ms	80532 KB	Execution timed out (wall clock limit exceeded)
25	Runtime error	363 ms	80532 KB	Execution timed out (wall clock limit exceeded)
26	Runtime error	373 ms	80532 KB	Execution timed out (wall clock limit exceeded)
27	Correct	579 ms	80532 KB	Output is correct
28	Runtime error	193 ms	80532 KB	Execution timed out (wall clock limit exceeded)
29	Runtime error	656 ms	80532 KB	Execution timed out (wall clock limit exceeded)
30	Runtime error	526 ms	80532 KB	Execution timed out (wall clock limit exceeded)
31	Runtime error	263 ms	80532 KB	Execution timed out (wall clock limit exceeded)
32	Runtime error	363 ms	80532 KB	Execution timed out (wall clock limit exceeded)
33	Runtime error	276 ms	80532 KB	Execution timed out (wall clock limit exceeded)
34	Correct	373 ms	80532 KB	Output is correct
35	Runtime error	249 ms	80532 KB	Execution timed out (wall clock limit exceeded)
36	Runtime error	603 ms	80532 KB	Execution timed out (wall clock limit exceeded)
37	Correct	313 ms	80532 KB	Output is correct
38	Correct	496 ms	80532 KB	Output is correct
39	Runtime error	246 ms	80532 KB	Execution timed out (wall clock limit exceeded)
40	Runtime error	369 ms	80532 KB	Execution timed out (wall clock limit exceeded)
41	Runtime error	423 ms	80532 KB	Execution timed out (wall clock limit exceeded)
42	Correct	603 ms	80532 KB	Output is correct