CF670C.Cinema

普及-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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 109.

In the evening after the conference, all n scientists decided to go to the cinema. There are m 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.

莫斯科正在举办一场重要的国际会议,有 nn 名来自不同国家的科学家参会。每名科学家恰好掌握一种语言。为方便起见,我们将世界上所有语言用 11 到 10910^9 之间的整数编号。

会议结束后的晚上,全部 nn 名科学家决定一同去电影院观影。他们前往的这家电影院共有 mm 部电影。每部电影由两个不同的整数刻画:音频语言的编号和字幕语言的编号。一名前往观看某部电影的科学家,若掌握该电影的音频语言,则会“非常满意”;若不掌握音频语言但掌握字幕语言,则会“基本满意”;若既不掌握音频语言也不掌握字幕语言,则会“不满意”(注意:对每部电影而言,其音频语言与字幕语言的编号总是不同的)。

科学家们决定共同观看同一部电影。你需要帮助他们选出一部电影,使得“非常满意”的科学家人数尽可能多。若有多个这样的电影,则在其中选择使“基本满意”的科学家人数最多的那一部。

输入格式

The first line of the input contains a positive integer n (1 ≤ n ≤ 200 000) — the number of scientists.

The second line contains n positive integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109), 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 ≤ 200 000) — the number of movies in the cinema.

The fourth line contains m positive integers _b_1, _b_2, ..., b__m (1 ≤ b__j ≤ 109), 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 ≤ 109), 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.

输入的第一行包含一个正整数 nn(1 ≤ n ≤ 200 0001 \leq n \leq 200\,000)—— 科学家的人数。

第二行包含 nn 个正整数 a1, a2, …, ana_1,\,a_2,\,\dots,\,a_n(1 ≤ ai ≤ 1091 \leq a_i \leq 10^9),其中 aia_i 表示第 ii 位科学家所掌握的语言编号。

第三行包含一个正整数 mm(1 ≤ m ≤ 200 0001 \leq m \leq 200\,000)—— 影院中电影的数量。

第四行包含 mm 个正整数 b1, b2, …, bmb_1,\,b_2,\,\dots,\,b_m(1 ≤ bj ≤ 1091 \leq b_j \leq 10^9),其中 bjb_j 表示第 jj 部电影的音频语言编号。

第五行包含 mm 个正整数 c1, c2, …, cmc_1,\,c_2,\,\dots,\,c_m(1 ≤ cj ≤ 1091 \leq c_j \leq 10^9),其中 cjc_j 表示第 jj 部电影的字幕语言编号。

保证每部电影的音频语言与字幕语言均不相同,即对所有 jj 均有 bj ≠ cjb_j \neq c_j。

输出格式

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 choose 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.

输出一个整数——即科学家们应当去观看的电影的编号。观看该电影后,感到“非常满意”的科学家人数应达到最大可能值。如果电影院中存在多个满足该条件的电影,则需从中选择一部,使得观看该电影后,“基本满意”的科学家人数达到最大可能值。

若存在多个可能的答案,输出其中任意一个即可。

输入输出样例

  • 输入#1

    3
    2 3 2
    2
    3 2
    2 3

    输出#1

    2
  • 输入#2

    6
    6 3 1 1 3 7
    5
    1 2 3 4 5
    2 3 4 5 1

    输出#2

    1

说明/提示

In the first sample, scientists must go to the movie with the index 2, as in such case the 1-th and the 3-rd scientists will be very pleased and the 2-nd scientist will be almost satisfied.

In the second test case scientists can go either to the movie with the index 1 or the index 3. After viewing any of these movies exactly two scientists will be very pleased and all the others will be not satisfied.

在第一个样例中,科学家们必须去看索引为 2 的电影,因为在这种情况下,第 1 位和第 3 位科学家将非常满意,而第 2 位科学家将基本满意。

在第二个测试用例中,科学家们可以去看索引为 1 或索引为 3 的电影。在观看其中任意一部电影后,恰好有两位科学家将非常满意,而其余所有科学家都将不满意。

输入解题思路,AI测评打分。不知道怎么写?

首页