Gold Balanced Lineup(hash)

*****
 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 using namespace std;
 6 const int N=100001;
 7 const int MOD=99991;
 8 int Maxdis,k;
 9 int c[N][32],sum[N][32];
10 int vis[N][32];
11 
12 struct node
13 {
14     int row_i;
15     struct node *next;
16 }*hash[N];
17 bool cmp(int a1,int b1)
18 {
19     for (int i = 0; i < k; i++)
20     {
21         if (c[a1][i]!=c[b1][i])
22             return false;
23     }
24     return true;
25 }
26 void Hash(int row_i)
27 {
28     int key = 0,i = 0;
29     while(i < k)
30     {
31         key = key*131+c[row_i][i];
32         i++;
33     }
34     key=abs(key)%MOD;
35     if (!hash[key])
36     {
37         hash[key] = new node;
38         hash[key]->row_i = row_i;
39         hash[key]->next = NULL;
40     }
41     else
42     {
43         struct node *p = hash[key];
44         if(cmp(p->row_i,row_i))
45         {
46             if (Maxdis < row_i-(p->row_i))
47                 Maxdis = row_i-(p->row_i);
48             return ;
49         }
50         while(p->next)
51         {
52             if (cmp(p->next->row_i,row_i))
53             {
54                 if (Maxdis < row_i-(p->next->row_i))
55                     Maxdis = row_i-(p->next->row_i);
56                 return ;
57             }
58             p = p->next;
59         }
60         p->next = new node;
61         p->next->row_i = row_i;
62         p->next->next = NULL;
63     }
64     return ;
65 }
66 int main()
67 {
68     int n;
69     scanf("%d %d",&n,&k);
70     for (int i = 0; i < k; i++)
71     {
72         c[0][i] = 0;
73         sum[0][i] = 0;
74     }
75     memset(hash,0,sizeof(hash));
76     Hash(0);
77     Maxdis = 0;
78     for (int i = 1; i <= n; i++)
79     {
80         int num;
81         scanf("%d",&num);
82         for (int j = 0; j < k; j++)
83         {
84             vis[i][j]=num%2;
85             num/=2;
86             sum[i][j] = sum[i-1][j]+vis[i][j];
87             c[i][j] = sum[i][j]-sum[i][0];
88         }
89         Hash(i);
90     }
91     printf("%d
",Maxdis);
92     return 0;
93 }
View Code