yeputons

Untitled

Jul 11th, 2012
149
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data