洛谷P6586 蒟蒻火锅的盛宴

传送门

题目背景

点击展开阅读更佳，题目背景与解题无关。

传说专门服务神仙们的蒟蒻火锅店前面有一首诗：

灶前无用煮青山，不识神炉自往还。

玉碗琼浆谁乞赐，瑶琴银箭可容攀。

风生夜气通云汉，雨歇秋光上碧湾。

却笑老奴真倦眼，此心空处一团闲。

Qiuly 是洛谷著名餐厅“蒟蒻火锅店”的主厨，当中的伙计很多，比如呆呆的 Aw 顿顿，机智的最蒟蒻的蒟蒻还有珂爱的 45dino。Qiuly 喜欢让顿顿为他准备丰富多样的食材，制作火锅的必需品包括但不限于七星章鱼和芥末鱼子酱，当然，还有各种各样珍稀而奇怪的食材：

蒟蒻果冻制成的蒟蒻团子。
糯米（雾）制成的糯米青团。
Aw 顿顿制成的菜鸡糕。
Bamboo（45dino）。
这些食材难以收集，但是神仙 Qiuly 还是全部弄到手了。接下来她要让顿顿分类这些食材。但是顿顿是菜鸡，根本不会分类，他崩溃了。于是他请你，IOI 的 AKer，帮助他分类这些食材，因为这个问题事关 Qiuly 的成绩（IOI 第一名还是第二名），所以你必须尽快。

每一个食材都有各种各样的奇怪特性，根据这些特性，Aw 顿顿咨询了全世界的专家们，评价出了一个食材的美味程度，根据这个程度可以有效的分类食材。如果你不能在 \bf 400400 毫秒内给出答案，你就会成为一个食材，光荣的沉没在 Qiuly 精心调制的汤底中。

题目描述

有 nn 个互不相同的整数，现有 mm 个整数属于集合 GG 中。

Aw顿顿规定这个集合有如下规定：

若 x\in Gx∈G，则 x+a\in Gx+a∈G。
若 x+ax+a 不在 nn 个整数中就不做处理。
若对于一个集合 GG 不存在需要加入的元素，那么它是完善的。
若集合是完善的，输出 Great Set!，反之输出至少还要按规定加入几个食材才能完善该级别。

输入格式

第一行是一个整数 nn，表示一共有 nn 个整数。

接下来一行存在 nn 个用空格隔开的整数 A_iA
i
​
，互不相同。

下一行一个正整数 mm，表示集合 GG 当中有 mm 个整数，均属于 nn 个整数当中。

接下来一行是 mm 个用空格隔开的整数。

最后是一个正整数 aa。

输出格式

如果这个集合已经完善，输出 Great Set!。

反之输出需要完善该集合所需的整数数量。

输入输出样例

输入 #1复制
5
1 2 3 4 5
3
1 3 5
2
输出 #1复制
Great Set!
输入 #2复制
15
13 2 10 3 1 12 8 4 5 7 9 6 15 14 11
7
13 2 1 12 8 3 10
2
输出 #2复制
8
输入 #3复制
50
13 2 10 50 1 28 37 32 30 46 19 47 33 41 24 34 27 42 49 18 9 48 23 35 31 8 7 12 6 5 3 22 43 36 11 40 26 4 44 17 39 38 15 14 25 16 29 20 21 45
10
50 46 30 32 10 2 28 37 1 13
3
输出 #3复制
31
说明/提示
【样例解释】
样例 1 解释
这个集合包含 1,3,51,3,5，其中 1+2=31+2=3，3+2=53+2=5，5+2=75+2=7 不存在，所以这个集合是完善的。

样例 2 解释
剩下的所有整数都属于这个集合。

【数据范围】
1\le m 4
。
1\le A_i\le n1≤A
i
​
≤n。
0\le a\le 10^40≤a≤10
4
。
【捆绑测试情况】
测试点编号 时间限制 分数分配 n,m\len,m≤
\rm Subtask 1Subtask1 \rm 400ms400ms \rm 10pts10pts 10^310
3

\rm Subtask 2Subtask2 \rm 400ms400ms \rm 15pts15pts 10^410
4

\rm Subtask 3Subtask3 \rm 400ms400ms \rm 35pts35pts 3\times 10^43×10
4

\rm Subtask 4Subtask4 \rm 400ms400ms \rm 40pts40pts 6\times 10^46×10
4

\rm P.S.P.S. 这题的时限已经开到 \rm stdstd 的 \bf 1515 倍，附件内有部分测试点。

上代码：

#include 
#define MAX_N 60001
using namespace std;
int n,m,A[MAX_N],G[MAX_N],a,S[MAX_N];
int main(){
    cin >> n;
    for (int i = 1;i <= MAX_N;i++){
        S[i] = -1;
        A[i] = -1;
    }
    for (int i = 1;i <= n;i++){
        int x;
        cin >> x;
        A[x] = x;
    }
    cin >> m;
    for (int i = 1;i <= m;i++){
        cin >> G[i];
        S[G[i]] = G[i]; 
    }
    cin >> a;
    int t = 0;
    for (int i = 1;i <= m + t;i++){
        if(A[G[i] + a] != -1 && S[G[i] + a] == -1){
            t++;
            S[G[i] + a] = G[i] + a;
            G[m + t] = G[i] + a;
        }
    }
    if(t == 0)
        cout << "Great Set!" << endl;
    else
        cout << t << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35