Cod sursa(job #2514110)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 24 decembrie 2019 15:12:16
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const string file = "loto";
const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647, nmax = 105;

struct triple{
    short x, y, z;
    bool operator<(const triple &aux)const{
        return x+y+z < aux.x+aux.y+aux.z;
    }
};

int n, S, v[nmax], p;
triple m[nmax*nmax*nmax];

int mfind(int s)
{
    s = S-s;
    int lo = 1, hi = p, mid, ans = -1;
    for (mid = (lo+hi)/2; lo <= hi; mid = (lo+hi)/2)
        if (m[mid].x+m[mid].y+m[mid].z <= s){
            ans = mid;
            lo = mid+1;
        }else hi = mid-1;
    if (m[ans].x+m[ans].y+m[ans].z != s)
        ans = -1;
    return ans;
}

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> S;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k)
                if (v[i]+v[j]+v[k] <= S)
                    m[++p] = {i, j, k};
    sort(m+1, m+p+1);
    for (int i = 1; i <= p; ++i){
        int ans = mfind(m[i].x+m[i].y+m[i].z);
        if (ans == -1)
            continue;
        fout << m[i].x << " " << m[i].y << " " << m[i].z << " " << m[ans].x << " " << m[ans].y << " " << m[ans].z << "\n";
        return 0;
    }
    fout << "-1\n";
    return 0;
}