Cod sursa(job #2975483)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 6 februarie 2023 17:21:19
Problema Oite Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("oite.in");
ofstream fout("oite.out");

const int DIM = 1025;
const int HASH_VALUE = 1000007;
vector<pair<int, int>> hashTable[HASH_VALUE];

int c, l, sol;
int nums[DIM];

inline auto getAddress(int hash, int value) {
    for (auto it = hashTable[hash].begin(); it != hashTable[hash].end(); it++)
        if (it->first == value)
            return it;
    return hashTable[hash].end();
}

int main() {
    fin >> c >> l;
    for (int i = 1; i <= c; i++)
        fin >> nums[i];

    int sum = nums[1] + nums[2];
    hashTable[sum % HASH_VALUE].push_back(make_pair(sum, 1));
    for (int i = 3; i < c; i++) {
        for (int j = i + 1; j <= c; j++) {
            int value = l - nums[i] - nums[j];
            if (value < 0) continue;

            int hash = value % HASH_VALUE;
            auto hashAddress = getAddress(hash, value);
            if (hashAddress != hashTable[hash].end())
                sol += hashAddress->second;
        }

        for (int j = 1; j < i; j++) {
            int value = nums[j] + nums[i];
            int hash = value % HASH_VALUE;
            auto hashAddress = getAddress(hash, value);
            if (hashAddress == hashTable[hash].end())
                hashTable[hash].push_back(make_pair(value, 1));
            else
                hashAddress->second++;
        }
    }

    fout << sol;

    return 0;
}