Cod sursa(job #51044)

Utilizator flo_demonBunau Florin flo_demon Data 9 aprilie 2007 19:58:57
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.57 kb
#include <stdio.h>
#include <set>

using namespace std;

#define MAX 1030

int C, L, a[MAX];
int wool, m[MAX*MAX], m2[MAX*MAX];
int n, pivot, aux, pivot2;
int o1, o2, o3, o4, found, pos, rez;
FILE *fout = fopen("oite.out", "w");
set<pair< pair<int, int>, pair<int, int> > > mm;

void quickSort(int st, int dr);

int main()
{
    FILE *fin = fopen("oite.in", "r");
    fscanf(fin, "%d%d", &C, &L);
    for (int i = 1; i <= C; ++i)
        fscanf(fin, "%d", &a[i]);
    fclose(fin);
    
    for (int i = 1; i <= C; ++i)
        for (int j = i+1; j <= C; ++j)
        {
            wool = a[i] + a[j];
            m[n] = wool;
            m2[n] = i*1030 + j;
            n++;
        }
    
    int st, dr, mijl;
    quickSort(0, n-1);
    for (int i = 0; i < n; ++i)
    {
        if (m[i] > L / 2) break;
        st = i;
        dr = n-1;
        found = 0;
        while (st <= dr)
        {
            mijl = (st + dr) >> 1;
            if (m[mijl] == (L - m[i]))
            {
                found = mijl;
                break;
            }
            else
                if (m[mijl] < (L - m[i]))
                    st = mijl + 1;
                else
                    dr = mijl - 1;
        }
        if (found)
        {
            pos = found;
            while (m[pos] == L - m[i])
            {
                o1 = m2[i] / 1030;
                o2 = m2[i] % 1030;
                o3 = m2[mijl] / 1030;
                o4 = m2[mijl] % 1030;
                if (!(o1 == o2 || o1 == o3 || o1 == o4 || o2 == o3 || o2 == o4 || o3 == o4))
                {
                    if (o1 > o2)
                    {
                        aux = o1;
                        o1 = o2;
                        o2 = aux;
                    }
                    if (o1 > o3)
                    {
                        aux = o1;
                        o1 = o3;
                        o3 = aux;
                    }
                    if (o1 > o4)
                    {
                        aux = o1;
                        o1 = o4;
                        o4 = aux;
                    }
                    if (o2 > o3)
                    {
                        aux = o2;
                        o2 = o3;
                        o3 = aux;
                    }
                    if (o2 > o4)
                    {
                        aux = o2;
                        o2 = o4;
                        o4 = aux;
                    }
                    if (o3 > o4)
                    {
                        aux = o3;
                        o3 = o4;
                        o4 = aux;
                    }
                    if (!mm.count( make_pair( make_pair(o1, o2), make_pair(o3, o4) ) ) )
                    {
                        mm.insert(make_pair( make_pair(o1, o2), make_pair(o3, o4) ) );
                        rez++;
                      //  fprintf(fout, "%d %d %d %d\n", o1, o2, o3, o4);
                    }
                }
                pos++;
                if (pos >= n) break;
            }
            
            pos = found-1;
            while (m[pos] == L - m[i])
            {
                o1 = m2[i] / 1030;
                o2 = m2[i] % 1030;
                o3 = m2[mijl] / 1030;
                o4 = m2[mijl] % 1030;
                if (!(o1 == o2 || o1 == o3 || o1 == o4 || o2 == o3 || o2 == o4 || o3 == o4))
                {
                    if (o1 > o2)
                    {
                        aux = o1;
                        o1 = o2;
                        o2 = aux;
                    }
                    if (o1 > o3)
                    {
                        aux = o1;
                        o1 = o3;
                        o3 = aux;
                    }
                    if (o1 > o4)
                    {
                        aux = o1;
                        o1 = o4;
                        o4 = aux;
                    }
                    if (o2 > o3)
                    {
                        aux = o2;
                        o2 = o3;
                        o3 = aux;
                    }
                    if (o2 > o4)
                    {
                        aux = o2;
                        o2 = o4;
                        o4 = aux;
                    }
                    if (o3 > o4)
                    {
                        aux = o3;
                        o3 = o4;
                        o4 = aux;
                    }
                    if (!mm.count( make_pair( make_pair(o1, o2), make_pair(o3, o4) ) ) )
                    {
                        mm.insert(make_pair( make_pair(o1, o2), make_pair(o3, o4) ) );
                        rez++;
                       // fprintf(fout, "%d %d %d %d\n", o1, o2, o3, o4);
                    }
                }
                pos--;
                if (pos < 0) break;
            }
        }
    }
    
    
    fprintf(fout, "%d\n", rez);
    fclose(fout);
    
    return 0;
}

void quickSort(int st, int dr)
{
    int i = st - 1, j = dr + 1;
    pivot = m[st];
    pivot2 = m2[st];
    do
    {
        do { i++; } while ((pivot > m[i]));
        do { j--; } while ((pivot < m[j]));
        if (i <= j)
        {
            aux = m[i];
            m[i] = m[j];
            m[j] = aux;
            
            aux = m2[i];
            m2[i] = m2[j];
            m2[j] = aux;
        }
    } while (i <= j);
    
    if (i < dr) quickSort(i, dr);
    if (j > st) quickSort(st, j);
}