Cod sursa(job #1749944)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 29 august 2016 12:24:20
Problema Oite Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define BYTE 0xff+1
#define getByte(X,Y) (*(((unsigned char *)&X)+Y))
#define NR_BYTES (sizeof(uint32_t))
#define MAX_N 10000000 + 1

using namespace std;

ifstream f ("oite.in");
ofstream t ("oite.out");

int32_t c,l,s=0;
const int key=47,mod=1049000;

int32_t v[1028];
pair <int32_t,int32_t> hsh[mod+10];

void increment(int32_t &i)
{
    if (++i==mod) i=0;
}

int32_t hashsum(int32_t x)
{
    return (1LL*x*key+x/key)%mod;
}

void hash_add(int32_t x)
{
    int32_t i=hashsum(x);
    for (; hsh[i].first!=x and hsh[i].first!=0; increment(i));
    if (hsh[i].first==0){
    hsh[i].first=x;
    hsh[i].second=1;}
    else ++hsh[i].second;
}

int32_t hash_find(int32_t x)
{
    int32_t cnt=0,i=hashsum(x);
    for (; hsh[i].first!=0 and hsh[i].first!=x; increment(i));
        if (hsh[i].first==x) cnt+=hsh[i].second;
    return cnt;
}

void spoof()
{
    for (int i = 1; i < c; ++i) {
        for (int j = i + 1; j < c; ++j)
            if (l-v[i]-v[j]>=0)
                s += hash_find(l - v[i] - v[j]);
        for (int j = 0; j < i; ++j)
            hash_add(v[i] + v[j]);
    }
}

int main()
{
    f>>c>>l;
    for (uint16_t i=0; i<c; ++i)
        f>>v[i];
    spoof();
    t<<s;
    return 0;
}