PAT Class A 1145 Hash - Average Lookup Time

Original title link

The task of this question is simple:

First insert an integer sequence consisting of several different positive integers into a hash table, then try to find another integer key value sequence from the table, and output the average search time (the search time refers to finding a valuewhether the number of comparison operations performed in the table).

The hash function is defined as H(key)=key%TSize, where TSize is the maximum size of the hash table.

Use quadratic probing with only positive increments to resolve conflicts.

Note that the size of the hash table is preferably a prime number, if the maximum size given by the user is not a prime number, the table size must be redefined to be the smallest prime number larger than the size given by the user.

Input format
The first line contains three positive integers MSize,N,M, which respectively represent the size of the user-defined table, the number of inserted integers, and the number of lookup key values.

The second line contains N distinct positive integers representing the insertion sequence.

The third line contains M positive integers representing key-value sequences.

The numbers in the same row are separated by spaces, and neither sequence contains more than 105 integers.

Output format
If some numbers cannot be inserted, they are output in sequence as follows, one line per number:

X cannot be inserted.
Where X represents a number that cannot be inserted.

The last line outputs the average search time of M searches, rounded to one decimal place.

Note: If TSize times are searched, and there are numbers in each search position, but not equal to the number to be searched, the search time is considered to be TSize+1.

Data Range
1≤MSize,N,M≤104
Sample input:
4 5 4
10 6 415 11
11 4 15 2
Sample output:
15 cannot be inserted.
2.8

My solution:

#include using namespace std;const int N = 10010;int n, m, s;int h[N];bool is_prime(int n){if(n == 1) return false;for(int i = 2; i * i <= n; i ++ ){if(n % i == 0) return false;}return true;}int find(int x, int &count){int t = x % s;for(int i = 0; i < s; i ++ ){int j = (t + i * i) % s;if(h[j] == 0 || h[j] == x) return j;else count ++ ;}return -1;}int main(){cin >> s >> n >> m;while(!is_prime(s)) s++;for(int i = 0; i < n; i ++ ){int x, count = 1;cin >> x;int t = find(x, count);if(t == -1) printf("%d cannot be inserted.\n", x);else h[t] = x;}int cnt = 0;for(int i = 0; i < m; i ++ ){int x, count = 1;cin >> x;int t = find(x, count);cnt += count;}printf("%.1lf", (double) cnt / m);return 0;}

Harvest:

Hash lookup and store value use the same function