Cod sursa(job #51055)

Utilizator flo_demonBunau Florin flo_demon Data 9 aprilie 2007 20:09:58
Problema Oite Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 kb
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>

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 found, pos, rez;
vector<int> o;
set<vector<int> > mm;
FILE *fout = fopen("oite.out", "w");

void quickSort(int st, int dr);

int main()
{
    o.resize(4);
    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])
            {
                o[0] = m2[i] / 1030;
                o[1] = m2[i] % 1030;
                o[2] = m2[pos] / 1030;
                o[3] = m2[pos] % 1030;
                sort(o.begin(), o.end());
                if (!(o[0] == o[1] || o[0] == o[2] || o[0] == o[3] || o[1] == o[2] || o[1] == o[3] || o[2] == o[3]))
                {
                    if (!mm.count(o))
                    {
                        mm.insert(o);
                        rez++;
                    }
                }
                pos++;
                if (pos >= n) break;
            }
            
            pos = found-1;
            while (m[pos] == L - m[i])
            {
                o[0] = m2[i] / 1030;
                o[1] = m2[i] % 1030;
                o[2] = m2[pos] / 1030;
                o[3] = m2[pos] % 1030;
                sort(o.begin(), o.end());
                if (!(o[0] == o[1] || o[0] == o[2] || o[0] == o[3] || o[1] == o[2] || o[1] == o[3] || o[2] == o[3]))
                {
                    if (!mm.count(o))
                    {
                        mm.insert(o);
                        rez++;
                    }
                }
                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];
    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);
}