fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. #define ll long long
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11.  
  12. const ll MAXN = 1e2 + 5;
  13. const ll MOD = 1e9 + 7;
  14. const ll INF = 1e9 + 7;
  15.  
  16. void FastIO(){
  17.     ios_base::sync_with_stdio(false);
  18.     cin.tie(NULL); cout.tie(NULL);
  19. }
  20.  
  21. void fre(){
  22.     freopen(".inp", "r", stdin);
  23.     freopen(".out", "w", stdout);
  24. }
  25.  
  26. int n, m, pre[1 << 9], cnt[1 << 9];
  27. vector<pair<int, int> > price[1 << 9];
  28.  
  29. int F(int p1, int p2) {
  30.     int res = 0;
  31.     for (int i = 0; i < (1 << 9); ++i) {
  32.         if ((i & (p1 | p2)) == i) {
  33.             res += pre[i];
  34.         }
  35.     }
  36.     return res;
  37. }
  38.  
  39. void Recur2(int i, int j, int &best1, int &best2, int &x, int &y) {
  40.     if (j >= (1 << 9)) return;
  41.     if (cnt[i] && cnt[j]) {
  42.         int tmp = F(i, j);
  43.         if (make_pair(tmp, -price[i][0].first - price[j][0].first) > make_pair(best1, -best2)) {
  44.             best1 = tmp;
  45.             best2 = price[i][0].first + price[j][0].first;
  46.             x = price[i][0].second;
  47.             y = price[j][0].second;
  48.         }
  49.     }
  50.     Recur2(i, j + 1, best1, best2, x, y);
  51. }
  52.  
  53. void getAnswer(int i, int &best1, int &best2, int &x, int &y) {
  54.     if (i >= (1 << 9)) return;
  55.     if (cnt[i] >= 2) {
  56.         int tmp = F(i, i);
  57.         if (make_pair(tmp, -price[i][0].first - price[i][1].first) > make_pair(best1, -best2)) {
  58.             best1 = tmp;
  59.             best2 = price[i][0].first + price[i][1].first;
  60.             x = price[i][0].second;
  61.             y = price[i][1].second;
  62.         }
  63.     }
  64.     if (cnt[i]) {
  65.         Recur2(i, i + 1, best1, best2, x, y);
  66.     }
  67.     getAnswer(i + 1, best1, best2, x, y);
  68. }
  69.  
  70. int main()
  71. {
  72.     FastIO();
  73.     cin >> n >> m;
  74. 	for (int i = 0; i < n; ++i) {
  75. 		int f, b;
  76. 		cin >> f;
  77. 		int cnt2 = 0;
  78. 		while (f--) {
  79. 			cin >> b;
  80. 			cnt2 ^= (1 << (b - 1));
  81. 		}
  82. 		++pre[cnt2];
  83. 	}
  84. 	for (int i = 1; i <= m; ++i) {
  85. 		int c, f, b, cnt2 = 0;
  86. 		cin >> c >> f;
  87. 		while (f--) {
  88. 			cin >> b;
  89. 			cnt2 ^= (1 << (b - 1));
  90. 		}
  91. 		++cnt[cnt2];
  92. 		price[cnt2].emplace_back(c, i);
  93. 	}
  94. 	for (int i = 0; i < (1 << 9); ++i) sort(price[i].begin(), price[i].end());
  95.     int x = 1, y = 2;
  96.     int best1 = -1, best2 = 2e9;
  97.     getAnswer(0, best1, best2, x, y);
  98.     cout << x << ' ' << y;
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2
https://ideone.com/9NkiDH
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!