Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

2735ms勉强卡过hash(附代码)

Posted by louchiheng at 2016-03-31 19:33:18 on Problem 3349
#include<vector>
#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=99991;
vector<int>a[maxn];
struct snowflower
{
	int c[6];
}s[100001];
int n,i,j,tot,k,sum,t,tt;
void hash()
{
	sum=(s[i].c[0]+s[i].c[1]+s[i].c[2]+s[i].c[3]+s[i].c[4]+s[i].c[5])%maxn;
	a[sum].push_back(i);
}
bool judge(int x,int y)
{
	for(int i=0;i<6;++i)
	if(s[y].c[i]==s[x].c[0])
	{
		tot=0;
		t=i+1;
		tt=1;
		while(s[y].c[t]==s[x].c[tt])
		{
			t++;
			tt++;
			tot++;
			if(t==6)t=0;
		}
		if(tot>=5)return 1;
		tot=0;
		t=i-1;
		tt=1;
		if(t==-1)t=5;
		while(s[y].c[t]==s[x].c[tt])
		{
			t--;
			tt++;
			tot++;
			if(t==-1)t=5;
		}
		if(tot>=5)return 1;
	}
	return 0;
}
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
	    scanf("%d%d%d%d%d%d",&s[i].c[0],&s[i].c[1],&s[i].c[2],&s[i].c[3],&s[i].c[4],&s[i].c[5]);
	    hash();
	}
	for(i=0;i<maxn;++i)
	if(a[i].size()>1)
	{
		for(int j=0;j<a[i].size()-1;++j)
		for(int k=j+1;k<a[i].size();++k)
		if(judge(a[i][j],a[i][k]))
		{
			printf("Twin snowflakes found.\n");
			return 0;
		}
	}
	printf("No two snowflakes are alike.\n");
//	fclose(stdin);
//	fclose(stdout);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator