#include <vector> #include <set> #include <algorithm> using namespace std; typedef long long ll; vector<int> ucs(vector<int> A, vector<int> B) { ll n = A.size(); multiset<int> m; // Používáme int, aby sedělo se vstupem // Naplnění multisety prvky z B for (int x : B) { m.insert(x); } vector<int> ans; ll ukazatel = 0; for (ll i = 0; i < n; i++) { int prvek = A[i]; // Pokud jsme už prošli celé B, nemá smysl pokračovat if (ukazatel >= B.size()) break; // Podíváme se, jestli prvek vůbec v zbývající části B existuje auto it = m.find(prvek); if (it != m.end()) { // Prvek v multisetě je. Nyní musíme v B přeskákat všechno, co mu předchází. // 1. Mažeme prvky, které přeskakujeme while (ukazatel < B.size() && B[ukazatel] != prvek) { auto to_remove = m.find(B[ukazatel]); if (to_remove != m.end()) { m.erase(to_remove); } ukazatel++; } // 2. Pokud jsme našli shodu (neskončili jsme na konci pole) if (ukazatel < B.size()) { ans.push_back(prvek); // Smažeme nalezený prvek z multisety auto found = m.find(prvek); if (found != m.end()) { m.erase(found); } // DŮLEŽITÉ: Posuneme ukazatel za právě použitý prvek, // abychom ho v příštím cyklu nezkoumali znovu. ukazatel++; } } } return ans; }