Pagini recente » Cod sursa (job #695645) | Cod sursa (job #2665575) | Cod sursa (job #2184237) | Cod sursa (job #1961670) | Cod sursa (job #1370214)
#include <stdio.h>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#define VECTOR_SIZE 100
#define FIN "loto.in"
#define FOUT "loto.out"
using namespace std;
struct vector3{
int i,j,k;
};
struct celula{
vector3 vect;
int sum;
};
int N,S;
int v[VECTOR_SIZE];
int sume[VECTOR_SIZE*VECTOR_SIZE*VECTOR_SIZE];
FILE *in,*out;
int sol[6];
void loto(){
/*
std::map<int,vector3> hashTable;
for(int i=0,s=0; i < N; i++){
for(int j=0; j < N; j++){
for(int k=0; k < N; k++,s++){
vector3 aux {v[i],v[j],v[k]};
hashTable[v[i]+v[j]+v[k]] = aux;
}
}
}
bool found = false;
vector3 first,second;
for(std::map<int,vector3>::iterator it = hashTable.begin(); it != hashTable.end(); ++it){
int aux = it->first;
first = it->second;
try{
second = hashTable.at(S-aux);
found = true;
break;
}catch(std::out_of_range o){}
}
*/
std::unordered_map<int,vector3> hashTable;
for(int i=0,s=0; i < N; i++){
for(int j=0; j < N; j++){
for(int k=0; k < N; k++,s++){
vector3 aux {v[i],v[j],v[k]};
hashTable[v[i]+v[j]+v[k]] = aux;
}
}
}
bool found = false;
vector3 first,second;
for(auto it = hashTable.begin(); it != hashTable.end(); ++it){
int aux = it->first;
first = it->second;
try{
second = hashTable.at(S-aux);
found = true;
break;
}catch(std::out_of_range o){}
}
if(!found){
sol[0] = -1;
} else {
sol[0] = first.i;
sol[1] = first.j;
sol[2] = first.k;
sol[3] = second.i;
sol[4] = second.j;
sol[5] = second.k;
}
}
bool compare(celula c1, celula c2) { return (c1.sum<c2.sum); }
/*
void loto2(){
std::vector<celula> hashTable;
for(int i=0; i < N; i++){
for(int j=0; j < N; j++){
for(int k=0; k < N; k++){
vector3 vec_aux {v[i], v[j], v[k]};
celula aux {vec_aux, v[i]+v[j]+v[k]};
hashTable.push_back(aux);
}
}
}
sort(hashTable.begin(), hashTable.end(), compare);
for(std::vector<celula>::iterator it = hashTable.begin(); it != hashTable.end(); ++it){
printf("%d:(%d,%d,%d)\n", it->sum, (it->vect).i, (it->vect).j, (it->vect).k);
}
vector3 first{0,0,0}, second{0,0,0};
bool found = false;
for(int i=0; i < N && !found; i++){
for(int j=0; j < N && !found; j++){
for(int k=0; k < N && !found; k++){
if(v[i] + v[j] + v[k] >= S) continue;
first.i = v[i];
first.j = v[j];
first.k = v[k];
int sumAux = S - (v[i] + v[j] + v[k]);
int lower = 0;
int upper = hashTable.size() - 1;
//cautare binara
while(lower < upper){
if(lower == upper || lower == upper - 1){
if(hashTable[lower].sum == sumAux){
found = true;
second.i = hashTable[lower].vect.i;
second.j = hashTable[lower].vect.j;
second.k = hashTable[lower].vect.k;
} else if(hashTable[upper].sum == sumAux){
found = true;
second.i = hashTable[upper].vect.i;
second.j = hashTable[upper].vect.j;
second.k = hashTable[upper].vect.k;
}
break;
}
int mid = lower + (upper - lower) / 2;
if(hashTable[mid].sum == sumAux){
found = true;
second.i = hashTable[mid].vect.i;
second.j = hashTable[mid].vect.j;
second.k = hashTable[mid].vect.k;
break;
}
if(hashTable[mid].sum < sumAux){
lower = mid+1;
} else {
upper = mid-1;
}
}
}
}
}
if(!found){
sol[0] = -1;
} else {
sol[0] = first.i;
sol[1] = first.j;
sol[2] = first.k;
sol[3] = second.i;
sol[4] = second.j;
sol[5] = second.k;
}
}
*/
int main(){
in = fopen(FIN, "rt");
out = fopen(FOUT, "wt");
int res;
res = fscanf(in, "%d%d", &N, &S);
for(int i=0; i < N; i++){
res = fscanf(in, "%d", &v[i]);
}
res++;
loto();
if(sol[0] == -1){
fprintf(out, "-1");
} else {
for(int i=0; i < 6; i++){
fprintf(out, "%d ", sol[i]);
}
}
fclose(in);
fclose(out);
return 0;
}