| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
2735ms勉强卡过hash(附代码)#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator