Combine several algorithms into one small pipeline.
What to build
A program that transforms a list, removes repeats and then searches it.
Requirements
- Read the numbers and double each one, using
transformwith a function of your own. - Sort them, and remove the repeats.
- Print the resulting list.
- For each query, print
yesorno, usingbinary_search.
Input
The first line has n. The second line has n numbers. The third line has q. The fourth line has q numbers.
Output
The list, then one line per query.
Constraints
n and q are from 1 to 1000.
Example
Input:
4
3 1 3 2
2
4 5
Output:
2 4 6
yes
no
Why it works
Each algorithm depends on the last: unique needs sorted data, and so does binary_search, so the order of the steps matters.
Examples
Example 1 · Input
4 3 1 3 2 2 4 5
Expected output
2 4 6 yes no
Example 2 · Input
1 0 1 0
Expected output
0 yes
Hints
Hint 1
Sort first, because unique only removes neighbours.
Hint 2
v.erase(unique(v.begin(), v.end()), v.end()) removes the leftovers.
Hint 3
binary_search answers each query quickly.
Solution
Show one correct solution (try it yourself first)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int twice(int x) {
return x * 2;
}
int main() {
int n, q;
cin >> n;
vector<int> v(n);
for (int& x : v) cin >> x;
transform(v.begin(), v.end(), v.begin(), twice);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int x : v) cout << x << " ";
cout << endl;
cin >> q;
for (int i = 0; i < q; i++) {
int x;
cin >> x;
cout << (binary_search(v.begin(), v.end(), x) ? "yes" : "no") << endl;
}
return 0;
}