Cod sursa(job #51011)

Utilizator flo_demonBunau Florin flo_demon Data 9 aprilie 2007 18:28:04
Problema Oite Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <stdio.h>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

#define MAX 1030

int C, L, n, a[MAX], wool;
map<int, map<pair<int, int>, bool> > m;
map<int, map<pair<int, int>, bool> >::iterator start, end, it1, it2;
map<pair<int, int>, bool>::iterator start1, end1, start2, end2;
int solz;
vector<int> o;
map<vector<int>, bool> sol;

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);
    
    o.resize(4);
    for (int i = 1; i <= C; ++i)
        for (int j = i + 1; j <= C; ++j)
        {
            wool = a[i] + a[j];
            m[wool][ make_pair(i, j) ] = true;
        }
        
    start = m.begin();
    end = m.end();
    for (; start != end; ++start)           // pentru fiecare suma posibila de 2 oi
    {
        if ((*start).first > L / 2) break;
        it1 = start;   
        it2 = m.find(L-(*start).first);     // gasim ce suma ne trebuie sa aiba celelalate 2
        if (it2 == m.end()) continue;
        
        start1 = (*it1).second.begin();
        end1 = (*it1).second.end();
        for (; start1 != end1; ++start1)    // parcurgem lista de perechi a primului grup de oi
        {
            start2 = (*it2).second.begin(); // lista de perechi a celui de-al 2-lea grup
            end2 = (*it2).second.end();
            for (; start2 != end2; ++start2)
            {
                o[0] = (*start1).first.first;
                o[1] = (*start1).first.second;
                o[2] = (*start2).first.first;
                o[3] = (*start2).first.second;
                 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]) continue;
                sort(o.begin(), o.end());
                if (!sol.count(o))
                {
                    sol[o] = true;
                    solz++;
                   // printf("%d %d %d %d\n", o[0], o[1], o[2], o[3]);
                }
            }
        }
    }
    
    FILE *fout = fopen("oite.out", "w");
    fprintf(fout, "%d\n", solz);
    fclose(fout);

    return 0;
}