답안 #90478 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90478	2018-12-21T19:55:16 Z	radoslav11	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	17.4603 / 100	1000 ms	158760 KB

brunhilda

/*
	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #90478

Compilation message

Subtask #1 4.44444444444 / 20.0

Subtask #2 4.44444444444 / 20.0

Subtask #3 8.57142857143 / 60.0

Subtask #1
4.44444444444 / 20.0

Subtask #2
4.44444444444 / 20.0

Subtask #3
8.57142857143 / 60.0