Cod sursa(job #458537)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 25 mai 2010 11:07:14
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<fstream>
#include<algorithm>
#define inf "oite.in"
#define outf "oite.out"
#define CMax 1100
#define DMax 1100000
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int L,C;
int v[CMax];
int nr,rez;

struct suma { int t,a,b; };

suma s[DMax];

void read()
{
f>>C>>L;
for(int i=1; i<=C; i++) f>>v[i];
}

struct cmp
{
bool operator () (const suma &x, const suma &y)
    {
    if( x.t < y.t ) return true;
    return false;
    }
};

int cauta(int val,int st,int dr)
{
int m;
while( st<=dr )
    {
    m = (st+dr)>>1 ;
    if( s[m].t == val ) return m;
    else if( s[m].t < val ) st = m+1 ;
    else if( s[m].t > val ) dr = m-1;
    }
return -1;
}

bool merge(int i,int j) { return ( s[i].a != s[j].a && s[i].a != s[j].b && s[i].b != s[j].a && s[i].b != s[j].b ) ; }

void solve()
{
int p;
//toate sumele de 2 cifre
for(int i=1; i<C; i++)
    for(int j=i+1; j<=C; j++) s[++nr].t = v[i]+v[j] , s[nr].a = v[i] , s[nr].b = v[j];
//sortez sumele
sort( s+1, s+nr+1, cmp() );
//rezolv
for(int i=1; i<nr; i++)
    {
    if( L-s[i].t < 0 ) break;
    p = cauta( L-s[i].t , i+1, nr ) ;
    if( p!=-1 )
        {
        if( merge(i,p) ) rez++;
        int j=p-1;
        while( s[j].t == L-s[i].t )
            {
            if( merge(i,j) ) rez++;
            j--;
            }
        j = p+1;
        while( s[j].t == L-s[i].t )
            {
            if( merge(i,j) ) rez++;
            j++;
            }
        }
    }
g<< rez;
}

int main()
{
read(); solve();
f.close(); g.close();
return 0;
}