topic description
Moscow is hosting a major international conference, which is attended by \(n\) scientists from different countries. Each of the scientists knows exactly one language. For convenience, we enumerate all languages of the world with integers from \(1\) to \(10^9\) .
In the evening after the conference, all nnn scientists decided to go to the cinema. There are mmm movies in the cinema they came to. Each of the movies is characterized by two distinct numbers — the index of audio language and the index of subtitles language. The scientist, who came to the movie, will be very pleased if he knows the audio language of the movie, will be almost satisfied if he knows the language of subtitles and will be not satisfied if he does not know neither one nor the other (note that the audio language and the subtitles language for each movie are always different).
Scientists decided to go together to the same movie. You have to help them choose the movie, such that the number of very pleased scientists is maximum possible. If there are several such movies, select among them one that will maximize the number of almost satisfied scientists.
Portal
input output format
input format:
The first line of the input contains a positive integer \(n\) (1<=n<=200000 1 <=n<=200000 1<=n<=200000) — the number of scientists.
The second line contains \(n\) positive integers \(a_1,a_2,…,a_n (1<=a_i<=10^9 )\), where \ (a_i\) is the index of a language, which the \(i\) -th scientist knows.
The third line contains a positive integer \(m (1<=m<=200000 )\) — the number of movies in the cinema.
The four th line contains \(m\) positive integers \(b_1,b_2,…,b_m (1<=b_j<= 10^9 )\), where \(b_j\) is the index of the audio language of the \( j\) -th movie.
The fifth line contains \(m\) positive integers \(c_1,c_2,…,c_m (1<=c_j<=10^9 )\), where \(c_j\) is the index of subtitles language of the \(j\) -th movie.
It is guaranteed that audio languages and subtitles language are different for each movie , that is \(b_j≠c_j\) .
output format:
Print the single integer — the index of a movie to which scientists should go. After viewing this movie the number of very pleased scientists should be maximum possible. If in the cinema there are several such movies, you need to cho ose among them one, after viewing which there will be the maximum possible number of almost satisfied scientists.
If there are several possible answers print any of them.
input and output example:
input example #1:
32 3 223 22 3
input example #2:
66 3 1 1 3 751 2 3 4 52 3 4 5 1
Output sample #1:
2
Output sample #2:
h4>
1
Analysis
Directly in all movies, find the movie with the most dubbing language, but this There may be more than one kind of movies, so find the movie with the most subtitle language among these movies.
How do you know how many people know which language? We can discretize it, because the data for this question is as big as \(10^9\), so we need to use map, otherwise it will be MLE.
As for finding out which languages are spoken by the most people, I used the sorting method at first, but the data is too malignant and stuck at the 125th data point, so I tried manually opening \(o_2\), still can’t make it. . . . . . So I had to give up sort and searched it manually.
code
//#pragma GCC optimize(2)#include#include #include
< /p>