fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <unordered_map>
  5. #include <algorithm>
  6.  
  7. int main() {
  8.     int N;
  9.     std::cin >> N;
  10.  
  11.     std::vector<int> A(N), B(N), C(N);
  12.     std::unordered_map<int, std::vector<int>> posA, posB, posC;
  13.  
  14.     for (int i = 0; i < N; ++i) {
  15.         std::cin >> A[i];
  16.         posA[A[i]].push_back(i);
  17.     }
  18.     for (int i = 0; i < N; ++i) {
  19.         std::cin >> B[i];
  20.         posB[B[i]].push_back(i);
  21.     }
  22.     for (int i = 0; i < N; ++i) {
  23.         std::cin >> C[i];
  24.         posC[C[i]].push_back(i);
  25.     }
  26.  
  27.     std::unordered_set<int> kept_indices;
  28.     for (int i = 0; i < N; ++i) {
  29.         kept_indices.insert(i);
  30.     }
  31.  
  32.     std::unordered_set<int> SA, SB, SC;
  33.     for (int i = 0; i < N; ++i) {
  34.         SA.insert(A[i]);
  35.         SB.insert(B[i]);
  36.         SC.insert(C[i]);
  37.     }
  38.  
  39.     while (true) {
  40.         bool changed = false;
  41.  
  42.         // Find mismatched events
  43.         std::unordered_set<int> to_remove_A, to_remove_B, to_remove_C;
  44.         for (int e : SA) {
  45.             if (SB.count(e) == 0 || SC.count(e) == 0) {
  46.                 to_remove_A.insert(e);
  47.             }
  48.         }
  49.         for (int e : SB) {
  50.             if (SA.count(e) == 0 || SC.count(e) == 0) {
  51.                 to_remove_B.insert(e);
  52.             }
  53.         }
  54.         for (int e : SC) {
  55.             if (SA.count(e) == 0 || SB.count(e) == 0) {
  56.                 to_remove_C.insert(e);
  57.             }
  58.         }
  59.  
  60.         if (to_remove_A.empty() && to_remove_B.empty() && to_remove_C.empty()) {
  61.             break;
  62.         }
  63.  
  64.         // Remove indices
  65.         std::unordered_set<int> indices_to_remove;
  66.         for (int e : to_remove_A) {
  67.             for (int idx : posA[e]) {
  68.                 indices_to_remove.insert(idx);
  69.             }
  70.             SA.erase(e);
  71.         }
  72.         for (int e : to_remove_B) {
  73.             for (int idx : posB[e]) {
  74.                 indices_to_remove.insert(idx);
  75.             }
  76.             SB.erase(e);
  77.         }
  78.         for (int e : to_remove_C) {
  79.             for (int idx : posC[e]) {
  80.                 indices_to_remove.insert(idx);
  81.             }
  82.             SC.erase(e);
  83.         }
  84.  
  85.         for (int idx : indices_to_remove) {
  86.             if (kept_indices.erase(idx)) {
  87.                 changed = true;
  88.                 // Update SA, SB, SC if needed
  89.                 int a = A[idx], b = B[idx], c = C[idx];
  90.                 if (std::none_of(kept_indices.begin(), kept_indices.end(), [&](int i){ return A[i] == a; })) {
  91.                     SA.erase(a);
  92.                 }
  93.                 if (std::none_of(kept_indices.begin(), kept_indices.end(), [&](int i){ return B[i] == b; })) {
  94.                     SB.erase(b);
  95.                 }
  96.                 if (std::none_of(kept_indices.begin(), kept_indices.end(), [&](int i){ return C[i] == c; })) {
  97.                     SC.erase(c);
  98.                 }
  99.             }
  100.         }
  101.  
  102.         if (!changed) {
  103.             break;
  104.         }
  105.     }
  106.  
  107.     int deletions = N - kept_indices.size();
  108.     std::cout << deletions << std::endl;
  109.  
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/5k89GV
language:
C++ (gcc 8.3)
created:
18 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!