CodeForces 670C Cinema(排序,离散化)

C. Cinema

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Input

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 a1, a2, ..., an (1 ≤ ai ≤ 109), where ai 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 b1, b2, ..., bm (1 ≤ bj ≤ 109), where bj is the index of the audio language of the j-th movie.

The fifth line contains m positive integers c1, c2, ..., cm (1 ≤ cj ≤ 109), where cj 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 bj ≠ cj.

Output

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.

Examples

input

3
2 3 2
2
3 2
2 3

output

2

input

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

output

1

bi为第一关键字,ci为第二关键字,排序,先离散化一下

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>

using namespace std;
#define MAX 200000
int a[MAX+5];
int n,m;
struct Node
{
    int pos;
    int x,y;
}b[MAX+5];
map<int,int> m1;
int num[MAX+5];
int cmp(Node x,Node y)
{
    if(num[x.x]==num[y.x])
        return num[x.y]>num[y.y];
    return num[x.x]>num[y.x];
}

int main()
{
    scanf("%d",&n);
    m1.clear();
    int cnt=1;
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(!m1.count(x))
        {
            m1[x]=cnt;
            a[i]=cnt++;
        }
        else
            a[i]=m1[x];
    }
    memset(num,0,sizeof(num));
    for(int i=1;i<=n;i++)
        num[a[i]]++;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        b[i].x=m1[x];
        b[i].pos=i;
    }
    for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            b[i].y=m1[x];
        }

    sort(b+1,b+m+1,cmp);
    printf("%d\n",b[1].pos);
    return 0;

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

Remove Duplicates from Sorted Array II

问题:消除数组中重复次数超过三次的多余的数 分析:若ai-1==ai-2若ai也相等,则清楚ai class Solution { public: in...

30850
来自专栏calmound

Remove Nth Node From End of List

问题:删除距离末尾n个距离的结点 分析:先找出距离末尾n个距离的结点其距离开始的距离多少,然后再删除 /** * Definition for singly-...

34050
来自专栏calmound

Pascal's Triangle II

问题:输出杨辉三角的第n行 class Solution { public: vector<int> getRow(int rowIndex) { ...

29070
来自专栏calmound

Minimum Depth of Binary Tree

题意:二叉树的最小深度 注意   1.当root为空的时候直接返回0,因为MIN赋值很大,所以如果不单独预判的话会返回MIN         2.判断树的深度应...

36670
来自专栏calmound

Sort Colors

题意:将三种颜色排列,相同的颜色放在一起,依据红绿蓝012的顺序放置 分析:统计红绿蓝分别有多少个,然后重新给数组赋值 class Solution { pub...

36860
来自专栏calmound

Populating Next Right Pointers in Each Node

问题:将二叉树的所有结点指向他的右边的一个结点 分析:对于每一个结点来说,其操作都是一样的,除了他的左儿子指向右儿子外,其左儿子的全部右后辈均指向其右儿子的全部...

353100
来自专栏calmound

Search in Rotated Sorted Array

问题:找出某个元素的位置 朴素的暴力方法 class Solution { public: int search(int A[], int n, int...

30850
来自专栏calmound

Merge Two Sorted Lists

问题:有序合并两个有序链表 分析:归并排序的合并部分 class Solution { public: ListNode *mergeTwoLists(...

37040
来自专栏calmound

Swap Nodes in Pairs

问题:交换相邻的两个结点 分析:建立新链表每次插入ret->next后在插入ret,需要在判断下若最后只有一个结点不需要交换,注意每次交换了结点要把尾结点的下一...

31550
来自专栏calmound

Unique Paths

问题:从起点到终点总共有多少条路径 分析:f[x,y]=f[x+1,y]+f[x,y+1],用记忆化搜索就可以解决了 class Solution { publ...

34450

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励