Cod sursa(job #1762519)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 23 septembrie 2016 17:49:51
Problema Oite Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <stdio.h>
#include <stdlib.h>
#define MOD 666013
#define MAXN 1048576

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline int nextnum(){
    int a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}
class Hash{
    public: int k, next[MAXN+1], lista[MOD];
    int val[MAXN+1], d[MAXN+1];
    inline void insert(int x, int y){
        k++;
        val[k]=x;
        d[k]=y;
        next[k]=lista[x%MOD];
        lista[x%MOD]=k;
    }
    inline void erase(int x){
        int p=lista[x%MOD];
        if(p==0)
            return ;
        if(val[p]==x){
            lista[x%MOD]=next[lista[x%MOD]];
            return ;
        }
        while((next[p]!=0)&&(val[next[p]]!=x))
            p=next[p];
        if(next[p]!=0)
            next[p]=next[next[p]];
    }
    int find(int x){
        int p=lista[x%MOD];
        if(p==0)
            return -1;
        if(val[p]==x)
            return p;
        while(next[p]!=0 && val[next[p]]!=x)
            p=next[p];
        if(next[p]!=0)
            return p;
        return -1;
    }
} H1;

int v[1024];
int main(){
    fi=fopen("oite.in","r");
    fo=fopen("oite.out","w");
    //printf("da\n");
    int n=nextnum(), l=nextnum();
    //Hash H1;
    for(int i=0;i<n;i++)
        v[i]=nextnum();
    long long sol=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int rest=l-v[i]-v[j];
            if(H1.find(rest)!=-1)
                sol+=H1.d[H1.find(rest)];
        }
        for(int j=0;j<i;j++)
            if(H1.find(v[i]+v[j])==-1)
                H1.insert(v[i]+v[j], 1);
            else
                H1.d[H1.find(v[i]+v[j])]++;
    }
    fprintf(fo,"%lld", sol);
    fclose(fi);
    fclose(fo);
    return 0;
}