fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int n, n2;
  8. vector<vector<int>> result;
  9.  
  10. void dfs(vector<int> d, int idx, int sm, int mx, vector<int> temp, int num){
  11.     temp.push_back(num);
  12.     if (temp.size() == n){
  13.         sort(temp.begin(), temp.end());
  14.         vector<int> t;
  15.         for (int i = 0; i < n; i++){
  16.             for (int j = i + 1; j < n; j++){
  17.                 t.push_back(temp[j]-temp[i]);
  18.             }
  19.         }
  20.         sort(t.begin(), t.end());
  21.         bool bad = 1;
  22.         for (int i = 0; i < n2; i++){
  23.             if (d[i] != t[i]) {
  24.                 bad = 0;
  25.                 break;
  26.             }
  27.         }
  28.         if (bad) result.push_back(temp);
  29.         return;
  30.     }
  31.  
  32.     int l = d[idx]-sm, r = mx-d[idx];
  33.     for (int i = 0; i <= idx; i++){
  34.         if (d[i] == l){
  35.             dfs(d, idx-1, sm, mx, temp, l);
  36.         }
  37.         if (d[i] == r){
  38.             dfs(d, idx-1, sm, mx, temp, r);
  39.         }
  40.     }
  41. }
  42.  
  43. int main(){
  44.     cin >> n;
  45.     n2 = n*(n-1)/2;
  46.     vector<int> d(n2);
  47.     for (int i = 0; i < n2; i++){
  48.         cin >> d[i];
  49.     }
  50.     int mx = d[n2-1];
  51.     vector<int> temp = {0};
  52.     dfs(d, n2-2, 0, mx, temp, mx);
  53.     sort(result.begin(), result.end());
  54.     // for (int i = 0; i < result.size(); i++){
  55.     //     for (int j : result[i]) cout << j << " ";
  56.     //     cout << "\n";
  57.     // }
  58.     for (int i : result[0]) cout << i << " ";
  59.     cout << "\n";
  60.     for (int i : result[result.size()-1]) cout << i << " ";
  61.     return 0;
  62. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
1 2 3 3 5 5 6 8 10 11
stdout
copy 
0 1 3 6 11 
0 5 8 10 11
https://ideone.com/MJUFAu
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!