Cod sursa(job #458949)

Utilizator MurphYZoRMarius Eu de la 9B-re MurphYZoR Data 27 mai 2010 10:19:06
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
  #include<fstream> 
#include<algorithm> 
#include<bitset> 
using namespace std; 
  
typedef long long int64; 
  
ofstream fout("loto.out"); 
struct tri 
{ 
    int64 v; 
    int64 a, b, c; 
}; 
void read(); 
void doit(); 
int64 src(long long val); 
bool cmp(const tri& t1, const tri& t2) 
{ 
    return t1.v <= t2.v; 
} 
  
long long n, sm, v[101]; 
long long t = -1; 
tri tt[1000001]; 
bitset<300000001> is; 
  
int main() 
{ 
    read(); 
    doit(); 
    fout.close(); 
    return 0; 
} 
  
void read() 
{ 
    ifstream fin("loto.in"); 
    fin >> n >> sm; 
    for (long long i = 0; i < n; ++i) 
    fin >> v[i]; 
    fin.close(); 
} 
  
void doit() 
{ 
    for (int64 i = 0; i < n; ++i) 
        for (int64 j = 0; j < n; ++j) 
            for (int64 k = 0; k < n; ++k) 
                if (v[i] + v[j] + v[k] <= sm && is[v[i] + v[j] + v[k]] == 0) 
                { 
                    tt[++t].v = v[i] + v[j] + v[k]; 
                    tt[t].a = i, tt[t].b = j, tt[t].c = k; 
                    is[v[i] + v[j] + v[k]] = 1; 
                } 
    sort(tt, tt + t + 1, cmp); 
    for (int64 i = 0; i <= t; ++i) 
        if (src(sm - tt[i].v) != -1) 
        { 
            int64 ps = src(sm - tt[i].v); 
            fout << v[tt[i].a] << ' ' << v[tt[i].b] << ' ' << v[tt[i].c] << ' '
                 << v[tt[ps].a] << ' ' << v[tt[ps].b] << ' ' << v[tt[ps].c]; 
            return; 
        } 
    fout << -1; 
} 
  
int64 src(long long val) 
{ 
    int64 l1 = 0, l2 = t, p = -1; 
    while (l1 <= l2) 
    { 
        int64 md = (l1 + l2) >> 1; 
        if (tt[md].v == val) 
        { 
            p = md; 
           break; 
        } 
        if (tt[md].v > val) 
            l2 = md - 1; 
        else
            l1 = md + 1; 
    } 
    return p; 
}