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 | } |
