Cod sursa(job #2677183)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 25 noiembrie 2020 22:13:20
Problema Loto Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>	
#define debug(x) cerr << #x << " " << x << "\n"
#define debugsp(x) cerr << #x << " " << x << " "

using namespace std;

const int INF = 2e9;
const int N = 100;

struct Three {
  int a, b, c;
};

class HashMap {
private:
  const static int MOD = 666013;

  vector <pair <int, Three>> table[MOD];

public:

  bool Find(int elem) {
    int buck = elem % MOD;

    for(auto it : table[buck])
      if(it.first == elem) return true;
    return false;
  }

  Three _Find(int elem) {
    int buck = elem % MOD;

    for(auto it : table[buck])
      if(it.first == elem)
        return it.second;
  }

  void Insert(int elem, Three tpl) {
    int buck = elem % MOD;
    
    table[buck].push_back(make_pair(elem, tpl));
  }
};
HashMap mp;

int v[1 + N];
int tupl[3];
int n, s;

void Back(int cnt, int sum) {
  if(sum > s) return;
  if(cnt == 3) {
    if(mp.Find(s - sum)) {
      Three rest = mp._Find(s - sum);
      cout << tupl[0] << " " << tupl[1] << " " << tupl[2] << ' ';
      cout << rest.a << " " << rest.b << " " << rest.c << '\n';

      exit(0);
    }

    mp.Insert(sum, {tupl[0], tupl[1], tupl[2]});
    return;
  } else {
    for(int i = 1; i <= n; i++) {
      tupl[cnt] = v[i];
      Back(cnt + 1, sum + v[i]);
    }
  }
}

int main() {
  freopen("loto.in", "r", stdin);
  freopen("loto.out", "w", stdout);
  scanf("%d%d", &n, &s);

  for(int i = 1; i <= n; i++) scanf("%d", &v[i]);
  
  Back(0, 0);
  printf("-1\n");
  return 0;
}