Pagini recente » Borderou de evaluare (job #3179505) | Borderou de evaluare (job #3179507) | Borderou de evaluare (job #1510093) | Borderou de evaluare (job #1132651) | Cod sursa (job #974501)
Cod sursa(job #974501)
//O( (n^3)log(n^3) )
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<unsigned, unsigned short > ENTRY_T;
int bsearch(const vector<ENTRY_T> &sume,unsigned size, unsigned val){
unsigned lo=0, hi=size-1;
unsigned mid;
bool found=false;
while(lo<=hi&&!found){
mid=lo+(hi-lo)/2;
if(sume[mid].first<val) lo=mid+1;
else if(sume[mid].first==val){found=true;}
else hi=mid-1;
}
if(found) return mid;
else return -1;
}
int main(){
ifstream fin("loto.in");
ofstream fout("loto.out");
unsigned N,S;
fin>>N>>S;
vector<unsigned> numere(N);
for(unsigned i=0;i<N;++i) fin>>numere[i];
vector<ENTRY_T> sume(N*N*N);
unsigned c=0;
for(unsigned short i=0;i<N;++i)
for(unsigned short j=i;j<N;++j)
for(unsigned short k=j;k<N;++k){
sume[c].first=numere[i]+numere[j]+numere[k];
sume[c].second=(i<<8)|j;
++c;
}
sort(sume.begin(),sume.begin()+c);
bool found=false;
for(unsigned i=0;i<c&&(!found)&&sume[i].first<=S;++i){
int y=bsearch(sume,c,S-sume[i].first);
if(y>-1){
found=true;
vector<unsigned> out(6);
out[0]=numere[ (sume[i].second)>>8 ];
out[1]=numere[ (sume[i].second)&255 ];
out[2]=sume[i].first-out[0]-out[1];
out[3]=numere[ (sume[y].second)>>8 ];
out[4]=numere[ (sume[y].second)&255 ];
out[5]=sume[y].first-out[3]-out[4];
sort(out.begin(),out.end());
fout<<out[0]<<' '<<out[1]<<' '<<out[2]<<' '<<out[3]<<' '<<out[4]<<' '<<out[5]<<'\n';
}
}
if(!found) fout<<"-1\n";
return 0;
}