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

放心大胆地开数组吧...

Posted by zhangxiao1124 at 2008-05-05 16:02:20 on Problem 2785
#include<iostream>
using namespace std;
#define maxn 5000
#define bignum 19999999
#define Inf 219901124
int n,ans,a[4][maxn],hash[bignum+10],s[bignum+10];

void Init() {
    scanf("%d",&n);
    for (int i=0; i<n; i++)
        for (int j=0; j<4; j++) scanf("%d",&a[j][i]);
    fill_n(hash,bignum,Inf);
}

int Hash(int h) {
    h%=bignum;
    return (h>0)?h:h+bignum;
}

void Add(int num,int flag) {
    if (flag) num=-num;
    int h=Hash(num);
    while (hash[h]!=Inf && hash[h]!=num) {
        h++;
        if (h==bignum) h=0;
    } 
    if (flag) ans+=s[h];
    else hash[h]=num,s[h]++;
}

void Work() {
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            Add(a[0][i]+a[1][j],0);
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            Add(a[2][i]+a[3][j],1);
}

int main() {
    Init();
    Work();
    printf("%d\n",ans);
    return 0;
}

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