Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cmath>
- #include <cassert>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <deque>
- #include <queue>
- #include <map>
- #include <set>
- using namespace std;
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #define pb push_back
- #define mp make_pair
- #define sz(x) ((int)(x).size())
- typedef long long ll;
- typedef vector<ll> vll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- typedef vector<vb> vvb;
- typedef pair<int, int> pii;
- struct Ans {
- int ans;
- int a, b, c;
- Ans(int ans = 0, int a = -1, int b = -1, int c = -1) : ans(ans), a(a), b(b), c(c) {}
- int cnt() const { return (a >= 0) + (b >= 0) + (c >= 0); }
- bool operator<(const Ans &a2) const {
- if (ans != a2.ans) return ans < a2.ans;
- if (cnt() != a2.cnt()) return cnt() > a2.cnt();
- if (a != a2.a) return a > a2.a;
- if (b != a2.b) return b > a2.b;
- return c > a2.c;
- }
- };
- int main() {
- #ifdef DEBUG
- freopen("std.in", "r", stdin);
- freopen("std.out", "w", stdout);
- #endif
- int n, k, s;
- while (scanf("%d%d%d", &n, &k, &s) >= 1) {
- vvb good(s, vb(k, false));
- vvi ids(k);
- for (int i = 0; i < s; i++) {
- for (;;) {
- int x;
- scanf("%d", &x);
- if (!x) break;
- x--;
- good[i][x] = true;
- ids[x].pb(i);
- }
- }
- vi ord(n);
- for (int i = 0; i < n; i++)
- scanf("%d", &ord[i]), ord[i]--;
- Ans ans;
- vi firbad(s);
- for (int s1 = 0; s1 < s; s1++) {
- firbad[s1] = 0;
- while (firbad[s1] < n && good[s1][ord[firbad[s1]]])
- firbad[s1]++;
- }
- // One type
- for (int s1 = 0; s1 < s; s1++)
- ans = max(ans, Ans(firbad[s1], s1));
- vvi firbad2(s);
- // Two types
- for (int s1 = 0; s1 < s; s1++) {
- int b = firbad[s1];
- if (b >= n) continue;
- b = ord[b];
- firbad2[s1] = vi(sz(ids[b]), 0);
- for (int i = 0; i < sz(ids[b]); i++) {
- int s2 = ids[b][i];
- for (int i2 = 0; i2 < n; i2++) {
- if (good[s1][ord[i2]] || good[s2][ord[i2]]) {
- ans = max(ans, Ans(i2 + 1, s1, s2));
- firbad2[s1][i] = i2 + 1;
- } else
- break;
- }
- }
- }
- // Three types
- for (int s1 = 0; s1 < s; s1++) {
- int b = firbad[s1];
- if (b >= n) continue;
- b = ord[b];
- for (int i = 0; i < sz(ids[b]); i++) {
- int s3 = ids[b][i];
- int c = firbad2[s1][i];
- if (c >= n) continue;
- c = ord[c];
- for (int i2 = 0; i2 < sz(ids[c]); i2++) {
- int s2 = ids[c][i2];
- int cpos = firbad2[s1][i];
- while (cpos < n && (good[s1][ord[cpos]] || good[s2][ord[cpos]])) cpos++;
- while (cpos < n && (good[s2][ord[cpos]] || good[s3][ord[cpos]])) cpos++;
- ans = max(ans, Ans(cpos, s1, s2, s3));
- }
- }
- for (int i = 0; i < sz(ids[b]); i++) {
- int s2 = ids[b][i];
- int c = firbad2[s1][i];
- if (c >= n) continue;
- c = ord[c];
- for (int i2 = 0; i2 < sz(ids[c]); i2++) {
- int s3 = ids[c][i2];
- int cpos = firbad2[s1][i];
- while (cpos < n && (good[s2][ord[cpos]] || good[s3][ord[cpos]])) cpos++;
- ans = max(ans, Ans(cpos, s1, s2, s3));
- }
- }
- }
- printf("%d\n%d %d %d\n", ans.ans, ans.a + 1, ans.b + 1, ans.c + 1);
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment