SHOW:
|
|
- or go back to the newest paste.
1 | #include <cstdio> | |
2 | #include <cstdlib> | |
3 | #include <cstring> | |
4 | #include <cmath> | |
5 | #include <cassert> | |
6 | #include <algorithm> | |
7 | #include <string> | |
8 | #include <vector> | |
9 | #include <deque> | |
10 | #include <queue> | |
11 | #include <map> | |
12 | #include <set> | |
13 | ||
14 | using namespace std; | |
15 | ||
16 | #define eprintf(...) fprintf(stderr, __VA_ARGS__) | |
17 | #define pb push_back | |
18 | #define mp make_pair | |
19 | #define sz(x) ((int)(x).size()) | |
20 | ||
21 | typedef long long ll; | |
22 | typedef vector<ll> vll; | |
23 | typedef vector<int> vi; | |
24 | typedef vector<vi> vvi; | |
25 | typedef vector<bool> vb; | |
26 | typedef vector<vb> vvb; | |
27 | typedef pair<int, int> pii; | |
28 | ||
29 | struct Ans { | |
30 | int ans; | |
31 | int a, b, c; | |
32 | ||
33 | Ans(int ans = 0, int a = -1, int b = -1, int c = -1) : ans(ans), a(a), b(b), c(c) {} | |
34 | int cnt() const { return (a >= 0) + (b >= 0) + (c >= 0); } | |
35 | bool operator<(const Ans &a2) const { | |
36 | if (ans != a2.ans) return ans < a2.ans; | |
37 | if (cnt() != a2.cnt()) return cnt() > a2.cnt(); | |
38 | if (a != a2.a) return a > a2.a; | |
39 | if (b != a2.b) return b > a2.b; | |
40 | return c > a2.c; | |
41 | } | |
42 | }; | |
43 | ||
44 | int main() { | |
45 | #ifdef DEBUG | |
46 | freopen("std.in", "r", stdin); | |
47 | freopen("std.out", "w", stdout); | |
48 | #endif | |
49 | ||
50 | int n, k, s; | |
51 | while (scanf("%d%d%d", &n, &k, &s) >= 1) { | |
52 | vvb good(s, vb(k, false)); | |
53 | vvi ids(k); | |
54 | for (int i = 0; i < s; i++) { | |
55 | for (;;) { | |
56 | int x; | |
57 | scanf("%d", &x); | |
58 | if (!x) break; | |
59 | x--; | |
60 | good[i][x] = true; | |
61 | ids[x].pb(i); | |
62 | } | |
63 | } | |
64 | ||
65 | vi ord(n); | |
66 | for (int i = 0; i < n; i++) | |
67 | scanf("%d", &ord[i]), ord[i]--; | |
68 | ||
69 | Ans ans; | |
70 | vi firbad(s); | |
71 | for (int s1 = 0; s1 < s; s1++) { | |
72 | firbad[s1] = 0; | |
73 | while (firbad[s1] < n && good[s1][ord[firbad[s1]]]) | |
74 | firbad[s1]++; | |
75 | } | |
76 | ||
77 | // One type | |
78 | for (int s1 = 0; s1 < s; s1++) | |
79 | ans = max(ans, Ans(firbad[s1], s1)); | |
80 | ||
81 | vvi firbad2(s); | |
82 | ||
83 | // Two types | |
84 | for (int s1 = 0; s1 < s; s1++) { | |
85 | int b = firbad[s1]; | |
86 | if (b >= n) continue; | |
87 | b = ord[b]; | |
88 | ||
89 | firbad2[s1] = vi(sz(ids[b]), 0); | |
90 | for (int i = 0; i < sz(ids[b]); i++) { | |
91 | int s2 = ids[b][i]; | |
92 | ||
93 | for (int i2 = 0; i2 < n; i2++) { | |
94 | if (good[s1][ord[i2]] || good[s2][ord[i2]]) { | |
95 | ans = max(ans, Ans(i2 + 1, s1, s2)); | |
96 | firbad2[s1][i] = i2 + 1; | |
97 | } else | |
98 | break; | |
99 | } | |
100 | } | |
101 | } | |
102 | ||
103 | // Three types | |
104 | for (int s1 = 0; s1 < s; s1++) { | |
105 | int b = firbad[s1]; | |
106 | if (b >= n) continue; | |
107 | b = ord[b]; | |
108 | ||
109 | for (int i = 0; i < sz(ids[b]); i++) { | |
110 | int s3 = ids[b][i]; | |
111 | ||
112 | int c = firbad2[s1][i]; | |
113 | if (c >= n) continue; | |
114 | ||
115 | c = ord[c]; | |
116 | for (int i2 = 0; i2 < sz(ids[c]); i2++) { | |
117 | int s2 = ids[c][i2]; | |
118 | ||
119 | int cpos = firbad2[s1][i]; | |
120 | while (cpos < n && (good[s1][ord[cpos]] || good[s2][ord[cpos]])) cpos++; | |
121 | while (cpos < n && (good[s2][ord[cpos]] || good[s3][ord[cpos]])) cpos++; | |
122 | ans = max(ans, Ans(cpos, s1, s2, s3)); | |
123 | } | |
124 | } | |
125 | ||
126 | for (int i = 0; i < sz(ids[b]); i++) { | |
127 | int s2 = ids[b][i]; | |
128 | ||
129 | int c = firbad2[s1][i]; | |
130 | if (c >= n) continue; | |
131 | ||
132 | c = ord[c]; | |
133 | for (int i2 = 0; i2 < sz(ids[c]); i2++) { | |
134 | int s3 = ids[c][i2]; | |
135 | ||
136 | int cpos = firbad2[s1][i]; | |
137 | while (cpos < n && (good[s2][ord[cpos]] || good[s3][ord[cpos]])) cpos++; | |
138 | ans = max(ans, Ans(cpos, s1, s2, s3)); | |
139 | } | |
140 | } | |
141 | } | |
142 | ||
143 | printf("%d\n%d %d %d\n", ans.ans, ans.a + 1, ans.b + 1, ans.c + 1); | |
144 | } | |
145 | return 0; | |
146 | } |