Advertisement
erek1e

POI Task Squarks

Jul 18th, 2022
884
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  10.     int n; cin >> n;
  11.     int m = n*(n-1)/2;
  12.     vector<int> sum(m); // pairwise sums
  13.     for (int &x : sum) cin >> x;
  14.     sort(sum.begin(), sum.end());
  15.  
  16.     vector<vector<int>> answers;
  17.  
  18.     int s12 = sum[0], s13 = sum[1];
  19.     for (int p = 2; p < n; ++p) {
  20.         if (p > 2 && sum[p] == sum[p-1]) continue; // already considered same case
  21.         int s23 = sum[p];
  22.         if ((s12 + s13 + s23) & 1) continue;
  23.         if (s12 + s13 - s23 <= 0) continue;
  24.         int sum3 = (s12 + s13 + s23) / 2;
  25.  
  26.         multiset<int> s;
  27.         for (int x : sum) s.insert(x);
  28.         s.erase(s.lower_bound(s12)); // only erase once if multiple
  29.         s.erase(s.lower_bound(s13));
  30.         s.erase(s.lower_bound(s23));
  31.  
  32.         vector<int> ans{sum3-s23, sum3-s13, sum3-s12};
  33.  
  34.         bool works = true;
  35.         for (int i = 4; i <= n; ++i) {
  36.             int s1i = *s.begin();
  37.             ans.push_back(s1i-ans[0]);
  38.             if (ans[i-1] < ans[i-2]) {
  39.                 works = false;
  40.                 break;
  41.             }
  42.             // now erase all pairs of values of i with [1, i-1]
  43.             for (int j = 1; j < i; ++j) {
  44.                 int cur = ans[j-1] + ans[i-1];
  45.                 multiset<int>::iterator it = s.lower_bound(cur);
  46.                 if (*it != cur) {
  47.                     works = false;
  48.                     break;
  49.                 }
  50.                 s.erase(it);
  51.             }
  52.         }
  53.  
  54.         if (works) answers.push_back(ans);
  55.     }
  56.  
  57.     cout << answers.size() << endl;
  58.     for (vector<int> &ans : answers) {
  59.         for (int x : ans) cout << x << ' ';
  60.         cout << '\n';
  61.     }
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement