fork download
copy 
  1. #include "bits/stdc++.h"
  2. #ifdef PRINTERS
  3. #include "printers.hpp"
  4. using namespace printers;
  5. #define tr(a)        cerr<<#a<<": "<<a<<endl;
  6. #else
  7. #define tr(a)    
  8. #endif
  9. #define ll          long long
  10. #define pb          push_back
  11. #define mp          make_pair
  12. #define pii         pair<int,int>
  13. #define vi          vector<int>
  14. #define all(a)      (a).begin(),(a).end()
  15. #define F           first
  16. #define S           second
  17. #define sz(x)       (int)x.size()
  18. #define hell        1000000007
  19. #define endl        '\n'
  20. #define rep(i,a,b)    for(int i=a;i<b;i++)
  21. #define delta       idx
  22. #define gamma       temp
  23.  
  24. using namespace std;
  25.  
  26. vi delta;
  27. map<int,int>gamma;
  28. int n;
  29. bool recurse(int u){
  30.     if(u==n-2){
  31.         sort(all(idx));
  32.         for(auto j:idx)cout<<j<<" ";
  33.         cout<<endl;
  34.         return 1;
  35.     }
  36.     {
  37.         bool isGood=1;
  38.         idx.pb(temp.rbegin()->F);
  39.         vi erased;
  40.         rep(k,0,u+2){
  41.             auto it=temp.find(abs(idx[k]-idx.back()));
  42.             if(it==temp.end()){
  43.                 isGood=0;
  44.                 break;
  45.             }
  46.             else{
  47.                 erased.pb(it->F);
  48.                 it->S--;
  49.                 if(it->S==0)temp.erase(it);
  50.             }
  51.         }
  52.         if(isGood and recurse(u+1))return 1;
  53.         idx.pop_back();
  54.         for(auto i:erased)temp[i]++;
  55.     }
  56.     {
  57.         bool isGood=1;
  58.         idx.pb(idx[1]-temp.rbegin()->F);
  59.         vi erased;
  60.         rep(k,0,u+2){
  61.             auto it=temp.find(abs(idx[k]-idx.back()));
  62.             if(it==temp.end()){
  63.                 isGood=0;
  64.                 break;
  65.             }
  66.             else{
  67.                 erased.pb(it->F);
  68.                 it->S--;
  69.                 if(it->S==0)temp.erase(it);
  70.             }
  71.         }
  72.         if(isGood and recurse(u+1))return 1;
  73.         idx.pop_back();
  74.         for(auto i:erased)temp[i]++;
  75.     }
  76.     return 0;
  77. }
  78. void solve(){
  79.     gamma.clear();
  80.     delta.clear();
  81.     cin>>n;
  82.     rep(i,0,(n*(n-1))/2){
  83.         int alpha;
  84.         cin>>alpha;
  85.         gamma[alpha]++;
  86.     }
  87.     if(n==2){
  88.         cout<<0<<" "<<gamma.begin()->F<<endl;
  89.         return;
  90.     }
  91.     delta.pb(0);
  92.     delta.pb(gamma.rbegin()->F);
  93.     gamma.rbegin()->S--;
  94.     if(gamma.rbegin()->S==0){
  95.         gamma.erase(gamma.rbegin()->F);
  96.     }
  97.     assert(recurse(0));
  98. }
  99.  
  100. signed main(){
  101.     ios_base::sync_with_stdio(false);
  102.     cin.tie(0);
  103.     cout.tie(0);
  104.     int t=1;
  105.     cin>>t;
  106.     while(t--){
  107.         solve();
  108.     }
  109.     return 0;
  110. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
1
3
2 3 5
stdout
copy 
0 3 5
https://ideone.com/XKjeTC
language:
C++14 (gcc 8.3)
created:
6 years 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!