Cod sursa(job #1715318)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 10 iunie 2016 12:17:52
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 666013;

vector<pair<int,int>> hashTable[MOD];

uint32_t fhash(uint32_t v)
{
    return v * UINT32_C(2654435761);
}

void insert(int key)
{
    int bucket = fhash(key) % MOD;

    for (auto &it : hashTable[bucket])
    {
        if (it.first == key)
        {
            it.second++;
            return;
        }
    }

    hashTable[bucket].push_back({key, 1});
}

int search(int key)
{
    int bucket = fhash(key) % MOD;

    for (const auto &it : hashTable[bucket])
        if (it.first == key)
            return it.second;

    return 0;
}

constexpr int MAX_N = 1024;

int A[MAX_N];
int N, L;

int main()
{
    freopen("oite.in", "r", stdin);
    freopen("oite.out", "w", stdout);

    scanf("%d%d", &N, &L);

    for (int i = 1; i <= N; ++i)
        scanf("%d", &A[i]);

    long long solutions = 0;

    for (int i = 1; i <= N; ++i)
    {
        for (int j = i + 1; j <= N; ++j)
            if (L - A[i] + A[j] > 0)
                solutions += search(L - A[i] - A[j]);

        for (int j = 1; j < i; ++j)
            insert(A[i] + A[j]);
    }

    printf("%lld\n", solutions);

    return 0;
}