Cod sursa(job #3325577)

Utilizator Razvan23Razvan Mosanu Razvan23 Data 25 noiembrie 2025 19:25:23
Problema Hashuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 8.85 kb
Raporteaza aceasta sursa 
#include <bits/stdc++.h>
using namespace std;

// --- 1. PARSARE BUFFERIZATA (SECRETUL VITEZEI) ---
// Citeste blocuri mari de bytes in loc de caracter cu caracter
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;
    const int SIZE = 65536; // 64KB Buffer

    char read_ch() {
        if (sp == SIZE) {
            fread(buff, 1, SIZE, fin);
            sp = 0;
        }
        return buff[sp++];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[SIZE];
        sp = SIZE;
    }

    // Operator pentru citire int
    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch())); // Sarim peste spatii/nl
        n = c - '0';
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        return *this;
    }
};

class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;
    const int SIZE = 65536;

public:
    OutParser(const char* nume) {
        fout = fopen(nume, "w");
        buff = new char[SIZE];
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout); // Scriem ce a ramas in buffer la final
        delete[] buff;
        fclose(fout);
    }

    OutParser& operator << (int n) {
        if (n == 0) {
            write_ch('0');
            return *this;
        }
        // Conversie int -> char manuala (inversa)
        char temp[12];
        int k = 0;
        while (n) {
            temp[k++] = (n % 10) + '0';
            n /= 10;
        }
        while (k > 0) write_ch(temp[--k]);
        return *this;
    }

    OutParser& operator << (char c) {
        write_ch(c);
        return *this;
    }

    OutParser& operator << (const char* s) {
        while (*s) write_ch(*s++);
        return *this;
    }

    void write_ch(char c) {
        if (sp == SIZE) {
            fwrite(buff, 1, SIZE, fout);
            sp = 0;
        }
        buff[sp++] = c;
    }
};

// --- 2. MEMORIE STATICA GLOBALA ---
// O declaram global pentru a nu incarca stiva si pentru viteza maxima
const int N_HASH = 666013;
const int MAX_NODES = 1000005;

int head[N_HASH];
int val[MAX_NODES];
int urm[MAX_NODES];
int pos = 1;

// --- 3. CLASA TA (MODIFICATA PENTRU STATIC CHAINING) ---

template <typename T>
class Hash {
public:
    // Functie hash inline pentru viteza
    inline int getHash(int x) {
        // Amestecam bitii (simplu si rapid)
        x ^= x >> 16; x *= 0x85ebca6b;
        x ^= x >> 13; x *= 0xc2b2ae35;
        x ^= x >> 16;
        int res = x % N_HASH;
        if (res < 0) return res + N_HASH;
        return res;
    }

    void Insert(int x) {
        int h = getHash(x);

        // Verificare existenta (optional, dar cerut de Hashuri)
        for (int p = head[h]; p != 0; p = urm[p]) {
            if (val[p] == x) return;
        }

        // Adaugare la inceputul listei (O(1))
        val[pos] = x;
        urm[pos] = head[h];
        head[h] = pos;
        pos++;
    }

    void Delete(int x) {
        int h = getHash(x);
        int p = head[h];
        int ant = 0;

        while (p != 0) {
            if (val[p] == x) {
                if (ant == 0) head[h] = urm[p];
                else urm[ant] = urm[p];
                return;
            }
            ant = p;
            p = urm[p];
        }
    }

    bool Find(int x) {
        int h = getHash(x);
        for (int p = head[h]; p != 0; p = urm[p]) {
            if (val[p] == x) return true;
        }
        return false;
    }
};

// --- 4. CLASA DERIVATA (PROBLEMA SPECIFICA) ---

class Hashuri : public Hash<int>
{
    // Obiectele de citire/scriere
    InParser fin;
    OutParser fout;

public:
    Hashuri() : fin("hashuri.in"), fout("hashuri.out") { }

    void Rezolvare() {
        int n_ops, op, x;
        fin >> n_ops; // Citire rapida
        while(n_ops--) {
            fin >> op >> x;
            if (op == 1) Insert(x);
            else if (op == 2) Delete(x);
            else {
                fout << (Find(x) ? '1' : '0'); // Scriere rapida
                fout << '\n';
            }
        }
        // Destructorul lui OutParser va face flush la fisier automat
    }
};

int main() {
    // Nu mai avem nevoie de ios_base::sync_with_stdio(0)
    // pentru ca nu folosim cin/cout deloc.

    Hashuri A;
    A.Rezolvare();

    return 0;
}#include <bits/stdc++.h>
using namespace std;

// --- 1. PARSARE BUFFERIZATA (SECRETUL VITEZEI) ---
// Citeste blocuri mari de bytes in loc de caracter cu caracter
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;
    const int SIZE = 65536; // 64KB Buffer

    char read_ch() {
        if (sp == SIZE) {
            fread(buff, 1, SIZE, fin);
            sp = 0;
        }
        return buff[sp++];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[SIZE];
        sp = SIZE;
    }

    // Operator pentru citire int
    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch())); // Sarim peste spatii/nl
        n = c - '0';
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        return *this;
    }
};

class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;
    const int SIZE = 65536;

public:
    OutParser(const char* nume) {
        fout = fopen(nume, "w");
        buff = new char[SIZE];
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout); // Scriem ce a ramas in buffer la final
        delete[] buff;
        fclose(fout);
    }

    OutParser& operator << (int n) {
        if (n == 0) {
            write_ch('0');
            return *this;
        }
        // Conversie int -> char manuala (inversa)
        char temp[12];
        int k = 0;
        while (n) {
            temp[k++] = (n % 10) + '0';
            n /= 10;
        }
        while (k > 0) write_ch(temp[--k]);
        return *this;
    }

    OutParser& operator << (char c) {
        write_ch(c);
        return *this;
    }

    OutParser& operator << (const char* s) {
        while (*s) write_ch(*s++);
        return *this;
    }

    void write_ch(char c) {
        if (sp == SIZE) {
            fwrite(buff, 1, SIZE, fout);
            sp = 0;
        }
        buff[sp++] = c;
    }
};

// --- 2. MEMORIE STATICA GLOBALA ---
// O declaram global pentru a nu incarca stiva si pentru viteza maxima
const int N_HASH = 666013;
const int MAX_NODES = 1000005;

int head[N_HASH];
int val[MAX_NODES];
int urm[MAX_NODES];
int pos = 1;

// --- 3. CLASA TA (MODIFICATA PENTRU STATIC CHAINING) ---

template <typename T>
class Hash {
public:
    // Functie hash inline pentru viteza
    inline int getHash(int x) {
        // Amestecam bitii (simplu si rapid)
        x ^= x >> 16; x *= 0x85ebca6b;
        x ^= x >> 13; x *= 0xc2b2ae35;
        x ^= x >> 16;
        int res = x % N_HASH;
        if (res < 0) return res + N_HASH;
        return res;
    }

    void Insert(int x) {
        int h = getHash(x);

        // Verificare existenta (optional, dar cerut de Hashuri)
        for (int p = head[h]; p != 0; p = urm[p]) {
            if (val[p] == x) return;
        }

        // Adaugare la inceputul listei (O(1))
        val[pos] = x;
        urm[pos] = head[h];
        head[h] = pos;
        pos++;
    }

    void Delete(int x) {
        int h = getHash(x);
        int p = head[h];
        int ant = 0;

        while (p != 0) {
            if (val[p] == x) {
                if (ant == 0) head[h] = urm[p];
                else urm[ant] = urm[p];
                return;
            }
            ant = p;
            p = urm[p];
        }
    }

    bool Find(int x) {
        int h = getHash(x);
        for (int p = head[h]; p != 0; p = urm[p]) {
            if (val[p] == x) return true;
        }
        return false;
    }
};

// --- 4. CLASA DERIVATA (PROBLEMA SPECIFICA) ---

class Hashuri : public Hash<int>
{
    // Obiectele de citire/scriere
    InParser fin;
    OutParser fout;

public:
    Hashuri() : fin("hashuri.in"), fout("hashuri.out") { }

    void Rezolvare() {
        int n_ops, op, x;
        fin >> n_ops; // Citire rapida
        while(n_ops--) {
            fin >> op >> x;
            if (op == 1) Insert(x);
            else if (op == 2) Delete(x);
            else {
                fout << (Find(x) ? '1' : '0'); // Scriere rapida
                fout << '\n';
            }
        }
        // Destructorul lui OutParser va face flush la fisier automat
    }
};

int main() {
    // Nu mai avem nevoie de ios_base::sync_with_stdio(0)
    // pentru ca nu folosim cin/cout deloc.

    Hashuri A;
    A.Rezolvare();

    return 0;
}