fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int a[1001];
  5. int sign[1001][1001];// stores 0 if i and j have same sign else 1
  6. int mat[1001][1001];// matrix for storing the modulus of diference
  7.  
  8. /* in solve function I am first I am considering the 2nd element as negative and then computing all other elements 
  9. using sign array and then checking whether a[] justifies mat[][] or not.*/
  10. void solve(){
  11.     int i,j;
  12.     a[2]=-1*mat[1][2];
  13.     for(i=3;i<=n;++i){
  14.         if(sign[2][i]==0)
  15.             a[i]=-1*mat[1][i];
  16.         else
  17.             a[i]=mat[1][i];
  18.     }
  19.     /*for(i=1;i<=n;++i)
  20.         cout<<a[i];*/
  21.     int flag=1;
  22.     for(i=2;i<n;++i){
  23.         for(j=i+1;j<=n;++j){
  24.             if(abs(a[i]-a[j])!=mat[i][j]){
  25.                 flag=0;
  26.                 break;
  27.             }
  28.         }
  29.         if(flag==0)
  30.             break;
  31.     }
  32.     if(flag==1)
  33.         return;
  34.  
  35.     a[2]=abs(mat[1][2]);
  36.     for(i=3;i<=n;++i){
  37.         if(sign[2][i]==0)
  38.             a[i]=mat[1][i];
  39.         else
  40.             a[i]=-1*mat[1][i];
  41.     }
  42.  
  43.     for(i=2;i<n;++i){
  44.         for(j=i+1;j<=n;++j){
  45.             if(abs(a[i]-a[j])!=mat[i][j]){
  46.                 flag=0;
  47.                 break;
  48.             }
  49.         }
  50.     }
  51.   return;  
  52. }
  53. int main(){
  54.     ios_base::sync_with_stdio(false);
  55.     cin.tie(NULL);
  56.     a[1]=0;
  57.     int q,i,j,x;
  58.     memset(sign,0,sizeof(sign));
  59.     cin>>n>>q;
  60.     for(i=1;i<=n;++i){
  61.         for(j=1;j<=n;++j)
  62.             cin>>mat[i][j];
  63.     }
  64.    /* for(i=1;i<=n;++i){
  65.         for(j=1;j<=n;++j)
  66.             cout<<mat[i][j];
  67.     }*/
  68.     for(i=1;i<=n;++i){
  69.         for(j=1;j<=n;++j)
  70.             if(abs(mat[1][i]-mat[1][j])==mat[i][j]){
  71.                 sign[i][j]=0;
  72.             }else
  73.             sign[i][j]=1;
  74.             sign[j][i]=sign[i][j];
  75.     }
  76.  
  77.  
  78.     solve();
  79.     for(i=1;i<=n;++i)
  80.         cout<<a[i]<<" ";
  81.     cout<<endl;
  82.     while(q--){
  83.         cin>>x;
  84.         for(i=1;i<=n;++i){
  85.             cin>>mat[x][i];
  86.             mat[i][x]=mat[x][i];
  87.         }
  88.  
  89.         for(i=1;i<=n;++i){
  90.             if(abs(mat[1][x]-mat[1][i])==mat[i][x]){
  91.                 sign[i][x]=0;
  92.             }else
  93.             sign[i][x]=1;
  94.             sign[x][i]=sign[i][x];
  95.     }
  96.     solve();
  97.     for(i=1;i<=n;++i)
  98.         cout<<a[i]<<" ";
  99.     cout<<endl;
  100.     }
  101. return 0;
  102. }
Success #stdin #stdout 0s 23072KB
comments (?)
stdin
copy 
3 2
0 1 2
1 0 1
2 1 0
1
0 4 3
2
4 0 7
stdout
copy 
0 -1 -2 
0 -4 -3 
0 -4 3
https://ideone.com/scTMaE
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!