Cod sursa(job #2629375)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 20 iunie 2020 13:11:41
Problema Secventa 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"


/// {1, 2}, {1, 3} cele mai mici sume -> cautam care este suma {2, 3} -> aflam cel mai mic numar
/// {2, 3} este in primele n sume

int p, n;
const int P = 25000, N = 25000;
int sum[1 + P], ans[1 + N];
bool solve (int sum23) {
    if ((sum[1] + sum[2] - sum[sum23]) & 1)
        return false;
    ans[1] = (sum[1] + sum[2] - sum[sum23]) / 2;
    map <int, int> freq;
    for (int i = 1; i <= p; i++)
        freq[sum[i]]++;
    int j = 1;
    for (int nr = 2; nr <= n; nr++) {
        while (j <= p && not freq[sum[j]])
            j++;
        ans[nr] = sum[j] - ans[1];
        for (int i = 1; i < nr; i++) {
            if (not freq[ans[i] + ans[nr]])
                return false;
            freq[ans[i] + ans[nr]]--;
        }
    }
    cout << n << "\n";
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << "\n";
    return true;
}

int main () {
    freopen ("sume.in", "r", stdin);
    freopen ("sume.out", "w", stdout);
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    cin >> p;
    for (int i = 1; i <= p; i++)
        cin >> sum[i];
    sort (sum + 1, sum + p + 1);
    n = 2;
    while (n * (n - 1) / 2 < p)
        n++;
    if (n * (n - 1) / 2 != p) {
        cout << "-1\n";
        return 0;
    }
    int sum23 = 3;
    while (sum23 <= n && not solve (sum23))
        sum23++;
    if (sum23 > n)
        cout << "-1\n";
    return 0;
}