I have Time Limit for 10 tests. (1.042 seconds)

Here is the task:

Intersection of many

(Time: 1 sec. Memory: 16 MB)

Two unordered sets of integers are given (maybe with repetitions). To issue without repetition in ascending order all those numbers that are found in both sets.

Input data. The first line of the input file INPUT.TXT contains two integers N and M (1 ≤ N, M ≤ 300 000) - the number of elements of the first and second sets, respectively. The following lines contain first the N numbers of the first set, and then the M numbers of the second set. Numbers are separated by spaces or line breaks. Each of these numbers falls in the range from 0 to 105.

Output. In the output file OUTPUT.TXT you need to write in ascending order without repeating all the numbers that are included in both the first and the second set. Separate numbers with one space. If there are no such numbers, the output file should remain empty.

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int a, b; cin >> a>> b; vector <int> f; vector <int> s; vector <int> ans; for (int i = 0; i < a; i++) { int x; cin >> x; f.push_back(x); } for (int i = 0; i < b; i++) { int x; cin >> x; s.push_back(x); } sort(f.begin(), f.end()); sort(s.begin(), s.end()); int pred = f[0]; for (int i = 1; i < f.size(); i++) { if (f[i] == pred) { f.erase(f.begin() + i); i--; } else pred = f[i]; } pred = s[0]; for (int i = 1; i < s.size(); i++) { if (s[i] == pred) { s.erase(s.begin() + i); i--; } else pred = s[i]; } int n=0; for(int i=0;i<f.size();i++) for (int j = n; j < s.size(); j++) { //if (f[i] == pred) { break; n = j + 1; } if (f[i] < s[j]) { break; n = j + 1; } else if (f[i] == s[j]) { ans.push_back(f[i]); n = j + 1; break; } } for (int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } return 0; }
  • one
    Let the URL play. The first idea is to use sets ... - Harry
  • one
    @Harry task - FL4SH
  • Why it is f.erase(f.begin() + i); ? Why explicitly delete items? Your approach is correct, but a waste of time to erase kills everything. Remove nafig all erase and just do not save the same elements in ans . - AnT

4 answers 4

The idea of ​​the solution is absolutely correct, and the implementation is a curve.

Explicit deletion of duplicate elements from source arrays through a separate pass with erase in a loop is a waste of time, because of which the program does not fit into the allotted time.

(Even if you do such pre-cleaning of arrays, you would have to do it through std::unique followed by a single call to erase . Even then you would most likely have missed the time. And your erase in a loop is incredible deceleration.)

But in fact, no preliminary cleaning should be done, and repeating elements should be eliminated at the stage of formation of the result.

I understand the idea of ​​your implementation of merging / intersecting arrays through two nested loops, but it really hurts to be unreadable. The "symmetrical" implementation (see below) looks much more elegant.

 #include <vector> #include <algorithm> #include <iostream> #include <iterator> int main() { unsigned a, b; std::cin >> a >> b; std::vector<unsigned> f, s; std::copy_n(std::istream_iterator<unsigned>(std::cin), a, std::back_inserter(f)); std::copy_n(std::istream_iterator<unsigned>(std::cin), b, std::back_inserter(s)); std::sort(f.begin(), f.end()); std::sort(s.begin(), s.end()); unsigned prev = -1; unsigned i = 0, j = 0; while (i < f.size() && j < s.size()) { unsigned vf = f[i], vs = s[j]; if (vf == vs && vf != prev) std::cout << (prev = vf) << " "; i += (vf <= vs), j += (vs <= vf); } std::cout << std::endl; }

I did not begin to accumulate the result in a separate vector ans , but instead I immediately output it to std::cout . But it does not matter.

    Schematically (in syntax is not strong):

     int b[0..105]; cin >> a >> b; for (int i = 0; i < a; i++) { cin >> x; b[x] |= 1; } for (int i = 0; i < b; i++) { cin >> x; b[x] |= 2; } for (int i = 0; i <= 105; i++) { if(b[i] == 3) { cout << i; } }
    • one
      There is a strong suspicion that 105 in the condition of the problem is actually 10^5 with formatting lost during copy-paste. :) - Yaant
    • @Yaant Well, replace 105 with 100,000 - business. From memory we pass, and the rest is nonsense. - Akina

    C ++ like pseudocode. Must pass in time due to positive integers from a not very large interval.

     int max = 100000; int n; std::cin >> n; int m; std::cin >> m; bool* fst = new bool[max + 1]; // числа, входящие в первое множество std::fill(fst, fst + sizeof(fst), 0); bool* snd = new bool[max + 1]; // числа, входящие в первое множество std::fill(snd, snd + sizeof(snd), 0); for (int i = 0; i < n; ++i) { int index; std::cin >> index; fst[index] = 1; // отмечаем первое множество } for (int i = 0; i < m; ++i) { int index; std::cin >> index; snd[index] = 1; // отмечаем второе множество } for (int i = 0; i <= max; ++i) if (fst[i] && snd[i]) std::cout << i; // если отмечены оба, то выводим число
    • You can explain bool* fst = new bool[max + 1]; std::fill(used, fst + sizeof(fst), 0); bool* snd = new bool[max + 1]; std::fill(snd, snd + sizeof(snd), 0); bool* fst = new bool[max + 1]; std::fill(used, fst + sizeof(fst), 0); bool* snd = new bool[max + 1]; std::fill(snd, snd + sizeof(snd), 0); - FL4SH
    • The index in the array is equal to the number about which we want to know whether to give it back. The expression fst [123] = 1 means that the number 123 is in the first set, snd [123] = 1 - that it is in the second. - Victor Khovanskiy
    • @ FL4SH, This answer passed all the tests? - Yernar
    • @Yernar, I will say so stupidly "zakopipastil" this code and I loop. Not yet understood. - FL4SH

    If you select the Microsoft Visual C ++ 2008 compiler on the site, then this solution passes:

     #include <cstdio> #include <set> int main() { std::set<int> mySet; int *arr = new int[100000],N,M, c, i; scanf("%d %d", &N, &M); for (i = 0; i < N; ++i) { scanf("%d", &c); arr[c] = 1; } for (i = 0; i < M; ++i) { scanf("%d", &c); if (arr[c] == 1) mySet.insert(c); } for (std::set<int>::iterator it = mySet.begin(); it != mySet.end(); ++it) printf("%d ", *it); }