답안 #90479 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90479	2018-12-21T20:08:16 Z	radoslav11	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	38.5714 / 100	1000 ms	112632 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(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
10.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	236 ms	78712 KB	Output is correct
2	Execution timed out	1076 ms	79144 KB	Time limit exceeded
3	Correct	764 ms	79144 KB	Output is correct
4	Correct	193 ms	79144 KB	Output is correct
5	Correct	409 ms	79416 KB	Output is correct
6	Correct	241 ms	79416 KB	Output is correct
7	Correct	733 ms	79416 KB	Output is correct
8	Execution timed out	1071 ms	79416 KB	Time limit exceeded
9	Execution timed out	1096 ms	79672 KB	Time limit exceeded
10	Execution timed out	1083 ms	79672 KB	Time limit exceeded
11	Execution timed out	1088 ms	79672 KB	Time limit exceeded
12	Correct	182 ms	79672 KB	Output is correct
13	Execution timed out	1073 ms	79672 KB	Time limit exceeded
14	Execution timed out	1081 ms	79672 KB	Time limit exceeded
15	Execution timed out	1081 ms	79672 KB	Time limit exceeded
16	Execution timed out	1040 ms	79672 KB	Time limit exceeded
17	Correct	393 ms	79672 KB	Output is correct
18	Correct	204 ms	79672 KB	Output is correct

Subtask #2
10.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	292 ms	80136 KB	Output is correct
2	Correct	142 ms	81912 KB	Output is correct
3	Execution timed out	1087 ms	112632 KB	Time limit exceeded
4	Correct	567 ms	112632 KB	Output is correct
5	Execution timed out	1091 ms	112632 KB	Time limit exceeded
6	Correct	744 ms	112632 KB	Output is correct
7	Correct	265 ms	112632 KB	Output is correct
8	Correct	534 ms	112632 KB	Output is correct
9	Execution timed out	1094 ms	112632 KB	Time limit exceeded
10	Execution timed out	1086 ms	112632 KB	Time limit exceeded
11	Execution timed out	1084 ms	112632 KB	Time limit exceeded
12	Execution timed out	1091 ms	112632 KB	Time limit exceeded
13	Correct	334 ms	112632 KB	Output is correct
14	Correct	559 ms	112632 KB	Output is correct
15	Execution timed out	1087 ms	112632 KB	Time limit exceeded
16	Correct	142 ms	112632 KB	Output is correct
17	Execution timed out	1070 ms	112632 KB	Time limit exceeded
18	Execution timed out	1076 ms	112632 KB	Time limit exceeded

Subtask #3
18.5714285714 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1071 ms	112632 KB	Time limit exceeded
2	Execution timed out	1093 ms	112632 KB	Time limit exceeded
3	Execution timed out	1082 ms	112632 KB	Time limit exceeded
4	Execution timed out	1091 ms	112632 KB	Time limit exceeded
5	Correct	319 ms	112632 KB	Output is correct
6	Execution timed out	1090 ms	112632 KB	Time limit exceeded
7	Execution timed out	1079 ms	112632 KB	Time limit exceeded
8	Execution timed out	1087 ms	112632 KB	Time limit exceeded
9	Execution timed out	1088 ms	112632 KB	Time limit exceeded
10	Execution timed out	1081 ms	112632 KB	Time limit exceeded
11	Correct	959 ms	112632 KB	Output is correct
12	Execution timed out	1082 ms	112632 KB	Time limit exceeded
13	Execution timed out	1081 ms	112632 KB	Time limit exceeded
14	Execution timed out	1077 ms	112632 KB	Time limit exceeded
15	Execution timed out	1073 ms	112632 KB	Time limit exceeded
16	Execution timed out	1087 ms	112632 KB	Time limit exceeded
17	Execution timed out	1076 ms	112632 KB	Time limit exceeded
18	Execution timed out	1086 ms	112632 KB	Time limit exceeded
19	Correct	561 ms	112632 KB	Output is correct
20	Execution timed out	1091 ms	112632 KB	Time limit exceeded
21	Execution timed out	1090 ms	112632 KB	Time limit exceeded
22	Execution timed out	1090 ms	112632 KB	Time limit exceeded
23	Correct	454 ms	112632 KB	Output is correct
24	Correct	340 ms	112632 KB	Output is correct
25	Execution timed out	1093 ms	112632 KB	Time limit exceeded
26	Execution timed out	1084 ms	112632 KB	Time limit exceeded
27	Execution timed out	1088 ms	112632 KB	Time limit exceeded
28	Correct	499 ms	112632 KB	Output is correct
29	Execution timed out	1097 ms	112632 KB	Time limit exceeded
30	Execution timed out	1093 ms	112632 KB	Time limit exceeded
31	Correct	601 ms	112632 KB	Output is correct
32	Correct	745 ms	112632 KB	Output is correct
33	Correct	256 ms	112632 KB	Output is correct
34	Execution timed out	1085 ms	112632 KB	Time limit exceeded
35	Correct	520 ms	112632 KB	Output is correct
36	Execution timed out	1081 ms	112632 KB	Time limit exceeded
37	Correct	342 ms	112632 KB	Output is correct
38	Execution timed out	1082 ms	112632 KB	Time limit exceeded
39	Correct	407 ms	112632 KB	Output is correct
40	Execution timed out	1089 ms	112632 KB	Time limit exceeded
41	Correct	751 ms	112632 KB	Output is correct
42	Execution timed out	1080 ms	112632 KB	Time limit exceeded

답안 #90479

Compilation message

Subtask #1 10.0 / 20.0

Subtask #2 10.0 / 20.0

Subtask #3 18.5714285714 / 60.0

Subtask #1
10.0 / 20.0

Subtask #2
10.0 / 20.0

Subtask #3
18.5714285714 / 60.0