oj.uz

Submission #90478

# Submission time Handle Problem Language Result Execution time Memory
90478 2018-12-21T19:55:16 Z radoslav11 Brunhilda’s Birthday (BOI13_brunhilda) C++14
17.4603 / 100
 1000 ms 158760 KB 
/*
	There is a simple solution with upper bound on the time equal to O(MAX * log(log(MAX)) * log(MAX)) with DP and maintaining a heap. Probably the actual complexity is smaller.
*/

#include <bits/stdc++.h>
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int B = (int)1e7 + 42;
const int inf = B + 42;

int n, q;
int dp[B + 42], cnt[inf + 42];
int a[MAXN], lp[B + 42];

void read()
{
	cin >> n >> q;
	for(int i = 0; i < n; i++)
		cin >> a[i];
}

priority_queue<int, vector<int>, greater<int> > Q;
int last[MAXN];

void fix()
{
	while(!Q.empty() && cnt[Q.top()])
	{
		cnt[Q.top()]--;
		Q.pop();
	}
}

void solve()
{
	for(int i = 0; i < a[n - 1]; i++) dp[i] = 1;
	for(int i = a[n - 1]; i <= B; i++) dp[i] = inf;

	memset(lp, -1, sizeof(lp));
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j <= B; j += a[i])
			if(dp[j] != 1 && lp[j] == -1)
				lp[j] = i;
	}

	for(int i = 0; i < n - 1; i++)
		Q.push(1), last[i] = 1;

	forward_list<int> li;
	for(int d = a[n - 1]; d <= B; d++)
	{
		li.clear();

		int dummy = d;
		while(lp[dummy] != -1)
		{
			int D = a[lp[dummy]];
			li.push_front(lp[dummy]);
			while(dummy % D == 0) dummy /= D;
		}

		for(int i: li) cnt[last[i]]++;
		
		fix();	
		if(!Q.empty()) 
			chkmin(dp[d], Q.top() + 1);
	
		for(int i: li)
		{
			Q.push(dp[d]);
			last[i] = dp[d];
		}
	}

	while(q--)
	{
		int x;
		cin >> x;
		if(dp[x] == inf) cout << "oo" << endl;
		else cout << dp[x] << endl;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}

Subtask #1
4.44444444444 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 259 ms 78840 KB Output isn't correct
2 Execution timed out 1083 ms 79084 KB Time limit exceeded
3 Incorrect 793 ms 79084 KB Output isn't correct
4 Correct 208 ms 79084 KB Output is correct
5 Correct 419 ms 79680 KB Output is correct
6 Incorrect 254 ms 79680 KB Output isn't correct
7 Incorrect 733 ms 79680 KB Output isn't correct
8 Execution timed out 1094 ms 79680 KB Time limit exceeded
9 Execution timed out 1081 ms 79892 KB Time limit exceeded
10 Execution timed out 1081 ms 79892 KB Time limit exceeded
11 Execution timed out 1080 ms 79892 KB Time limit exceeded
12 Correct 167 ms 79892 KB Output is correct
13 Execution timed out 1076 ms 87632 KB Time limit exceeded
14 Execution timed out 1088 ms 87632 KB Time limit exceeded
15 Execution timed out 1067 ms 87632 KB Time limit exceeded
16 Execution timed out 1081 ms 87632 KB Time limit exceeded
17 Incorrect 459 ms 87632 KB Output isn't correct
18 Correct 207 ms 87632 KB Output is correct

Subtask #2
4.44444444444 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 87632 KB Output is correct
2 Correct 139 ms 87632 KB Output is correct
3 Execution timed out 1081 ms 114192 KB Time limit exceeded
4 Incorrect 613 ms 114192 KB Output isn't correct
5 Execution timed out 1079 ms 114192 KB Time limit exceeded
6 Incorrect 782 ms 114192 KB Output isn't correct
7 Correct 303 ms 114192 KB Output is correct
8 Incorrect 601 ms 114192 KB Output isn't correct
9 Execution timed out 1074 ms 114192 KB Time limit exceeded
10 Execution timed out 1086 ms 115796 KB Time limit exceeded
11 Execution timed out 1078 ms 115796 KB Time limit exceeded
12 Execution timed out 1073 ms 115796 KB Time limit exceeded
13 Incorrect 362 ms 115796 KB Output isn't correct
14 Incorrect 618 ms 115796 KB Output isn't correct
15 Execution timed out 1075 ms 115796 KB Time limit exceeded
16 Correct 118 ms 115796 KB Output is correct
17 Execution timed out 1092 ms 115796 KB Time limit exceeded
18 Execution timed out 1054 ms 117936 KB Time limit exceeded

Subtask #3
8.57142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 118132 KB Time limit exceeded
2 Execution timed out 1092 ms 118576 KB Time limit exceeded
3 Execution timed out 1091 ms 119072 KB Time limit exceeded
4 Execution timed out 1078 ms 119072 KB Time limit exceeded
5 Correct 353 ms 119072 KB Output is correct
6 Execution timed out 1091 ms 119072 KB Time limit exceeded
7 Correct 987 ms 119072 KB Output is correct
8 Execution timed out 1082 ms 122672 KB Time limit exceeded
9 Execution timed out 1077 ms 123116 KB Time limit exceeded
10 Execution timed out 1087 ms 123116 KB Time limit exceeded
11 Incorrect 967 ms 123116 KB Output isn't correct
12 Execution timed out 1067 ms 123116 KB Time limit exceeded
13 Execution timed out 1085 ms 123116 KB Time limit exceeded
14 Execution timed out 1087 ms 123116 KB Time limit exceeded
15 Execution timed out 1085 ms 123116 KB Time limit exceeded
16 Execution timed out 1086 ms 123116 KB Time limit exceeded
17 Execution timed out 1086 ms 123116 KB Time limit exceeded
18 Execution timed out 1084 ms 125168 KB Time limit exceeded
19 Incorrect 587 ms 125168 KB Output isn't correct
20 Execution timed out 1089 ms 125748 KB Time limit exceeded
21 Execution timed out 1082 ms 125748 KB Time limit exceeded
22 Execution timed out 1074 ms 126988 KB Time limit exceeded
23 Correct 482 ms 126988 KB Output is correct
24 Incorrect 359 ms 126988 KB Output isn't correct
25 Execution timed out 1085 ms 126988 KB Time limit exceeded
26 Execution timed out 1092 ms 126988 KB Time limit exceeded
27 Execution timed out 1075 ms 129884 KB Time limit exceeded
28 Incorrect 512 ms 129884 KB Output isn't correct
29 Execution timed out 1095 ms 129884 KB Time limit exceeded
30 Execution timed out 1093 ms 129884 KB Time limit exceeded
31 Incorrect 624 ms 129884 KB Output isn't correct
32 Incorrect 750 ms 129884 KB Output isn't correct
33 Incorrect 265 ms 129884 KB Output isn't correct
34 Correct 972 ms 129884 KB Output is correct
35 Incorrect 540 ms 129884 KB Output isn't correct
36 Execution timed out 1082 ms 158760 KB Time limit exceeded
37 Correct 318 ms 158760 KB Output is correct
38 Execution timed out 1089 ms 158760 KB Time limit exceeded
39 Incorrect 400 ms 158760 KB Output isn't correct
40 Execution timed out 1084 ms 158760 KB Time limit exceeded
41 Correct 417 ms 158760 KB Output is correct
42 Execution timed out 1091 ms 158760 KB Time limit exceeded