yeputons

Untitled

Jul 11th, 2012
31
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.46 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment