hash80pts求助,tle#9#10
查看原帖
hash80pts求助,tle#9#10
1100140
Ryoo楼主2024/12/1 15:12
#include <bits/stdc++.h>
using namespace std;
const int P = 131;
int n,pd[300005];
struct tname{
	char name[55];
	unsigned long long hash1;
}coach;
struct classmates{
	char name[55];
	unsigned long long hash1;
}cm[300005];
bool cmp1(classmates x,classmates y) {
	return x.hash1 < y.hash1;
}
unsigned long long dealhash(char *x) {
	int len = strlen(x);
	unsigned long long thash = 0;
	for(int i = 0; i < len; i++) {
		thash = thash*P + x[i]-'a'+1;
	}
	return thash;
}
int binary(unsigned long long h) {
	int l = 1, r = n, mid = (l+r)/2;
	while(l <= r) {
		if(h > cm[mid].hash1) {l = mid+1;mid = (l+r)/2;}
		else if(h <= cm[mid].hash1 && l != r) {r = mid;mid = (l+r)/2;}
		else if(l == r) {
			if(h == cm[mid].hash1) return l;
			else return -1;
		}
	}
	
}
int main() {
	
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%s", cm[i].name);
		cm[i].hash1 = dealhash(cm[i].name);
	}
	sort(cm+1,cm+1+n,cmp1);
	int m;
	scanf("%d", &m);
	for(int i = 1; i <= m; i++) {
		scanf("%s", coach.name);
		coach.hash1 = dealhash(coach.name);
		int pot = binary(coach.hash1);
		if(pot == -1) {
			printf("WRONG\n");
		}
		else if(pot != -1) {
			if(pd[pot] == 0) {
				pd[pot] = 1;
				printf("OK\n");
			}
			else printf("REPEAT\n");
			
		}
		
		coach.hash1 = 0;
		memset(coach.name,0,sizeof(coach.name));
		
		
	}
}
2024/12/1 15:12
加载中...