fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int findLargestValidFeatureSet(vector<int>& feature1, vector<int>& feature2) {
  5.     if (feature1.empty()) {
  6.         return 0;
  7.     }
  8.  
  9.     int n = feature1.size();
  10.     vector<pair<int, int>> pairs;
  11.  
  12.     for (int i = 0; i < n; ++i) {
  13.         pairs.push_back({feature1[i], feature2[i]});
  14.     }
  15.  
  16.     sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
  17.         if (a.first != b.first) {
  18.             return a.first < b.first;
  19.         }
  20.         return a.second > b.second;
  21.     });
  22.  
  23.     vector<int> tails;
  24.     for (const auto& p : pairs) {
  25.         int y = p.second;
  26.         auto it = lower_bound(tails.begin(), tails.end(), y);
  27.  
  28.         if (it == tails.end()) {
  29.             tails.push_back(y);
  30.         } else {
  31.             *it = y;
  32.         }
  33.     }
  34.  
  35.     return tails.size();
  36. }
  37.  
  38. int main() {
  39. 	int n, m;
  40. 	cin >> n;
  41.     vector<int> feature1(n);
  42.     for (int i=0;i<n;i++) cin >> feature1[i];
  43.     cin >> m;
  44.     vector<int> feature2(m);
  45. 	for (int i=0;i<m;i++) cin >> feature2[i];
  46.  
  47.     cout << findLargestValidFeatureSet(feature1, feature2) << endl;  // Output: 3
  48.  
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
4 5 3 1 2
5
2 1 3 4 5
stdout
copy 
2
https://ideone.com/4a073f
language:
C++14 (gcc 8.3)
created:
13 hours 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!