Cod sursa(job #3129882)

Utilizator dandragosDan Dragos dandragos Data 16 mai 2023 06:14:13
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <fstream>

using namespace std;

ifstream fin("loto.in");   // Deschide fișierul de intrare pentru citire
ofstream fout("loto.out"); // Deschide fișierul de ieșire pentru scriere

const int MOD_MAX = 666013;
const int N_MAX = 1e2;
const int TRIPLETE_MAX = N_MAX * N_MAX * N_MAX;

int v[N_MAX];

struct sum {
    int x, y, z;

    // Suprascrie operatorul '==' pentru a compara obiectele de tip 'sum'
    friend bool operator==(sum &a, sum &b) {
        return (a.x == b.x) && (a.y == b.y) && (a.z == b.z);
    }
};

class HashTable {
private:
    const int NIL = -1;
    int head[MOD_MAX];
    sum key[TRIPLETE_MAX];
    int nxt[TRIPLETE_MAX];
    int mod;
    int curr = 0;

public:
    HashTable(int x) {
        mod = x;

        for (int i = 0; i < mod; ++i)
            head[i] = NIL;
        for (int i = 0; i < N_MAX; ++i)
            nxt[i] = NIL;
    }

    int getkey(sum x) {
        int aux = x.x + x.y + x.z;
        while (aux < 0)
            aux += mod;
        return aux % mod;
    }

    int getkey(int x) {
        while (x < 0)
            x += mod;
        return x % mod;
    }

    void add(sum x) {
        int list = getkey(x);
        key[curr] = x;
        nxt[curr] = head[list];
        head[list] = curr;
        ++curr;
    }

    bool find(int x, sum &a) {
        int list = getkey(x);
        int it = head[list];
        while (it != NIL && key[it].x + key[it].y + key[it].z != x)
            it = nxt[it];

        if (it != NIL)
            a = key[it];

        return it != NIL;
    }

    void erase(sum x) {
        int list = getkey(x);
        int ant = head[list], it = nxt[ant];
        if (key[ant] == x) {
            head[list] = nxt[ant];
        }
        else {
            while (it != NIL && key[it] != x) {
                ant = it;
                it = nxt[it];
            }

            if (it != NIL) {
                nxt[ant] = nxt[it];
            }
        }
    }

    void eraseall(sum x) {
        int list = getkey(x);
        int ant = head[list], it;

        while (key[ant] == x)
            ant = nxt[ant];
        head[list] = ant;

        it = nxt[ant];
        while (it != NIL) {
            if (key[it] == x)
                nxt[ant] = nxt[it];

            ant = it;
            it = nxt[it];
        }
    }
};

HashTable ht(MOD_MAX);

int main() {
    int n, s;
    fin >> n >> s;
    for (int i = 0; i < n; ++i)
        fin >> v[i];

    sum sum1, sum2, aux;
    sum1.x = -1;
    for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < n; ++k) {
aux.x = v[i];
aux.y = v[j];
aux.z = v[k];
ht.add(aux);
if (ht.find(s - (v[i] + v[j] + v[k]), sum2))
sum1 = aux;
}
if (sum1.x == -1)
    fout << "-1\n";
else
    fout << sum1.x << ' ' << sum1.y << ' ' << sum1.z << ' ' << sum2.x << ' ' << sum2.y << ' ' << sum2.z << '\n';

fin.close();
fout.close();
return 0;
}