9402 - 简单哈希表

给定一个哈希表,大小为m,哈希函数为对m取模,对于冲突采用线性探查法。有n次操作:

1.存入一个正整数,如果已存在 ,则不存储

2.查询一个正整数是否存在

并且要求输出每次探查的次数

输入

第一行两个整数 n,m

下面有n行表示n此操作,每行有2个数 op、key,op=1表示存入key,op=2表示查询一个key是否存在

输出

有n行输出,每行对应每个操作,需要输出两个数字 如果op=1 输出数字是否存在('true'或者'false') 输出冲突的次数,如果op=2 输出数字是否存在(1表示存在;0表示不存在),以及探查的元素个数

样例

输入

8 4
2 128
1 128
2 903
1 240
1 195
2 128
1 11
2 11

输出

0 1
0
0 1
1
0
1 1
3
1 4

提示

下图为样例数据最终存储的情况

0 < n m \leq 10000 题目保证op=1的次数不超过m

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题