Pagini recente » Cod sursa (job #3359460) | Monitorul de evaluare | sandwich | Monitorul de evaluare | Cod sursa (job #3359464)
//sortare francu + cb francu(teoretic mai rapide)
//poate nu destul si va trebui sa folosesc 2 pointers
#include <bits/stdc++.h>
#define MAXN 100
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
int v[MAXN + 1];
struct elem{
int x, y, z, s;
};
vector <elem> g;
vector <int> pi;
vector <elem> gen(int n){
int i, j, k;
vector <elem> rez;
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
for(k = 1; k <= n; k++){
rez.push_back({v[i], v[j], v[k], v[i] + v[j] + v[k]});
}
}
}
return rez;
}
void francu_qsort(int st, int dr){
int b, e, pivot, aux;
b = st;
e = dr;
pivot = g[pi[(b + e) / 2]].s;
while(g[pi[b]].s < pivot){
b++;
}
while(g[pi[e]].s > pivot){
e--;
}
while(b < e){
aux = pi[b];
pi[b] = pi[e];
pi[e] = aux;
do{
b++;
}while(g[pi[b]].s < pivot);
do{
e--;
}while(g[pi[e]].s > pivot);
}
if(st < e){
francu_qsort(st, e);
}
if(e + 1 < dr){
francu_qsort(e + 1, dr);
}
}
int main()
{
int n, suma, i, j, ok;
elem aux;
fin >> n >> suma;
for(i = 1; i <= n; i++){
fin >> v[i];
}
g = gen(n);
pi.resize(g.size());
for(i = 0; i < pi.size(); i++){
pi[i] = i;
}
francu_qsort(0, pi.size() - 1);
// for(i = 0; i < pi.size(); i++){
// printf("%d ", g[pi[i]].s);
// }
i = ok = 0;
j = pi.size() - 1;
while(i < j && !ok){
while(g[pi[i]].s + g[pi[j]].s > suma){
j--;
}
if(g[pi[i]].s + g[pi[j]].s == suma){
ok = 1;
}
i++;
}
i--;
if(!ok){
fout << "-1\n";
}else{
fout << g[pi[i]].x << " " << g[pi[i]].y << " " << g[pi[i]].z << " " << g[pi[j]].x << " " << g[pi[j]].y << " " << g[pi[j]].z << "\n";
}
return 0;
}