#2687. T4 回转寿司餐厅

T4 回转寿司餐厅

题目背景

在一个热闹的回转寿司餐厅里,许多顾客正在享受美味的寿司。这个餐厅采用的是回转寿司的模式,寿司盘沿着传送带顺着轨道传递,每一位顾客可以在寿司盘经过自己面前时挑选自己喜欢的寿司。每一块寿司都有一个美味度,而每位顾客的胃口(也就是美食水平)也不同。每个顾客都会根据自己对美食的偏好决定是否品尝经过的寿司。

然而,餐厅的规则十分简单且严格——每块寿司只能被一位顾客吃掉。如果没有任何顾客愿意吃某块寿司,那么这块寿司就无法被享用,最终它会被浪费掉。你被餐厅的老板委派,任务是根据每个顾客的美食水平与每块寿司的美味度,判断每一块寿司是否会被顾客吃掉,并输出第一个吃掉该寿司的顾客编号。如果没有人吃掉这块寿司,你应该输出 -1

你能完成这个任务并让所有的寿司都不被浪费掉吗?你需要通过以下方式帮助餐厅安排每个寿司的“食客”!

题目描述

在一个回转寿司餐厅中,有 NN 个顾客和 MM 块寿司。每块寿司都会按照顺序经过每个顾客。顾客会根据自己对寿司的喜好(即“美食水平”)决定是否吃掉寿司。如果某个顾客的美食水平 AiA_i 小于等于寿司的美味度 BjB_j,那么该顾客就会吃掉这块寿司。每块寿司只能被一个顾客吃掉,如果没有任何顾客愿意吃这块寿司,应该输出 -1

你需要确定每一块寿司是否被某个顾客吃掉,并且输出第一个吃掉该寿司的顾客编号。如果没有顾客吃掉该寿司,则输出 -1

输入格式

第一行包含两个整数 NNMM,分别表示顾客人数和寿司块数。

第二行包含 NN个整数,表示每个顾客的美食水平 AiA_i

第三行包含 MM个整数,表示每块寿司的美味度BiB_i

输出格式

对于每一块寿司,输出第一个吃掉它的顾客的编号。如果没有顾客吃掉该寿司,输出 -1

样例 #1

样例输入 #1

3 3
3 8 2
5 2 1

样例输出 #1

1
3
-1

样例1解释:

第一块寿司的美味度是 5,第 1 个人的美食水平是 3,所以第 1 个人吃掉了它。

第二块寿司的美味度是 2,第 1 个人的美食水平是 3,所以第 1 个人不吃,接着第 3 个人的美食水平是 2,刚好可以吃,所以第 3 个人吃掉了它。

第三块寿司的美味度是 1,所有人的美食水平都高于 1,所以没有人吃这块寿司,输出 -1

样例输入 #2

3 3
1 1 1
1 1 1

样例输出 #2

1
1
1

样例2解释:

每块寿司的美味度为 1,每个人的美食水平也为 1,所有人都能吃掉每一块寿司,因此每块寿司都会被第一个人吃掉。

数据范围

  • 对于 10% 的数据:

    1N,M1000 1 \leq N, M \leq 1000

    1Ai2000 1 \leq A_i \leq 2000 Bi B_i 值相同

  • 对于 50% 的数据:

    1N,M1000 1 \leq N, M \leq 1000

    1Ai,Bi5000 1 \leq A_i, B_i \leq 5000

  • 对于 100% 的数据:

    1N,M2×105 1 \leq N, M \leq 2 \times 10^5

    1Ai,Bi5×105 1 \leq A_i, B_i \leq 5 \times 10^5