POI Task Squarks

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int m = n*(n-1)/2;
    vector<int> sum(m); // pairwise sums
    for (int &x : sum) cin >> x;
    sort(sum.begin(), sum.end());

    vector<vector<int>> answers;

    int s12 = sum[0], s13 = sum[1];
    for (int p = 2; p < n; ++p) {
        if (p > 2 && sum[p] == sum[p-1]) continue; // already considered same case
        int s23 = sum[p];
        if ((s12 + s13 + s23) & 1) continue;
        if (s12 + s13 - s23 <= 0) continue;
        int sum3 = (s12 + s13 + s23) / 2;

        multiset<int> s;
        for (int x : sum) s.insert(x);
        s.erase(s.lower_bound(s12)); // only erase once if multiple
        s.erase(s.lower_bound(s13));
        s.erase(s.lower_bound(s23));

        vector<int> ans{sum3-s23, sum3-s13, sum3-s12};

        bool works = true;
        for (int i = 4; i <= n; ++i) {
            int s1i = *s.begin();
            ans.push_back(s1i-ans[0]);
            if (ans[i-1] < ans[i-2]) {
                works = false;
                break;
            }
            // now erase all pairs of values of i with [1, i-1]
            for (int j = 1; j < i; ++j) {
                int cur = ans[j-1] + ans[i-1];
                multiset<int>::iterator it = s.lower_bound(cur);
                if (*it != cur) {
                    works = false;
                    break;
                }
                s.erase(it);
            }
        }

        if (works) answers.push_back(ans);
    }

    cout << answers.size() << endl;
    for (vector<int> &ans : answers) {
        for (int x : ans) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}