#2946. 二分查找模板题1

二分查找模板题1

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定长度为 nn严格递增数组 aa,再给出 mm 个数。现要将这 mm 个数插入数组中,使得数组仍然保持严格递增。求这 mm 个数的插入位置和最后的数组。

如果有相同的数,你应该忽略这次操作。

输入格式

当前的输入为操作的密匙 xx。记上次的数(成功插入的数,忽略的不算)在原数组中的位置为 lastanslastans(如是第一次操作,lastans=0lastans=0),则本次的数为 xlastansx\oplus lastans

如仍对上述有疑惑,请看下面的 样例解释

第一行两个整数 n,mn,m

第二行 nn 个整数 aia_i,中间用空格隔开。保证 aa 数组严格递增。

接下来 mm 行,每行一个正整数表示密匙。

输出格式

第一行 mm 个正整数表示每个数的插入位置。如该数被忽略请输出 1-1

第二行输出若干个数表示最终数组。

样例 #1

样例输入 #1

5 4
1 3 10 14 20
5
5
15
21

样例输出 #1

3 4 6 8 
1 3 5 6 10 12 14 17 20

提示

样例解释

第一次,x=5,lastans=0x=5,lastans=0,则插入的数为 50=55\oplus 0=5

第二次,x=5,lastans=3x=5,lastans=3,则插入的数为 53=65\oplus 3=6

第三次,x=15,lastans=3x=15,lastans=3,则插入的数为 153=1215\oplus 3=12

第四次,x=21,lastans=4x=21,lastans=4,则插入的数为 214=1721\oplus 4=17

数据范围

对于 20%20\% 的数据,1n,m5001\leq n,m\leq 500

对于 40%40\% 的数据,1n,m50001\leq n,m\leq 5000

对于 100%100\% 的数据,1n,m1051\leq n,m\leq 10^51ai5×1051\leq a_i\leq 5\times 10^5

不保证异或之后的插入数 51055*10^5

第二届小云雀杯初级组

未参加
状态
已结束
规则
IOI
题目
5
开始于
2023-4-22 20:00
结束于
2023-4-22 22:15
持续时间
2.3 小时
主持人
参赛人数
327