Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2020
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ctime>
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define f first
  7. #define s second
  8. #define mp make_pair
  9. #define ll long long
  10.  
  11. #define MAXN 200005
  12. #define INF 1000000009
  13. #define MOD 1000000007
  14. #define EPS 0.001
  15.  
  16. int gauss (vector < vector< double > > a, vector<double> & ans) {
  17.     int n = (int) a.size();
  18.     int m = (int) a[0].size() - 1;
  19.    
  20.     unsigned int pre_time = clock();
  21.     unsigned int start_time = pre_time;
  22.  
  23.     vector<int> where (m, -1);
  24.     for (int col=0, row=0; col<m && row<n; ++col) {
  25.         if((col+1) % 10 == 0){
  26.             cerr << (long double)(col+1) / 100.0 << "% : ";
  27.             cerr << (long double)(clock() - start_time) / 1000000.0 << " | " << (long double)(clock() - pre_time) / 1000000.0 << " sec\n";
  28.             pre_time = clock();
  29.         }
  30.         int sel = row;
  31.         for (int i=row; i<n; ++i)
  32.             if (abs (a[i][col]) > abs (a[sel][col]))
  33.                 sel = i;
  34.         if (abs (a[sel][col]) < EPS)
  35.             continue;
  36.         for (int i=col; i<=m; ++i)
  37.             swap (a[sel][i], a[row][i]);
  38.         where[col] = row;
  39.  
  40.         for (int i=0; i<n; ++i)
  41.             if (i != row) {
  42.                 double c = a[i][col] / a[row][col];
  43.                 for (int j=col; j<=m; ++j)
  44.                     a[i][j] -= a[row][j] * c;
  45.             }
  46.         ++row;
  47.     }
  48.  
  49.     cerr << "end col after " << (double)(clock() - start_time) / 1000000.0 << " sec" << endl;
  50.  
  51.     ans.assign (m, 0);
  52.     for (int i=0; i<m; ++i)
  53.         if (where[i] != -1)
  54.             ans[i] = a[where[i]][m] / a[where[i]][i];
  55.     for (int i=0; i<n; ++i) {
  56.         double sum = 0;
  57.         for (int j=0; j<m; ++j)
  58.             sum += ans[j] * a[i][j];
  59.         if (abs (sum - a[i][m]) > EPS)
  60.             return 0;
  61.     }
  62.  
  63.     for (int i=0; i<m; ++i)
  64.         if (where[i] == -1)
  65.             return INF;
  66.     return 1;
  67. }
  68.  
  69. void solve(){
  70.     int n;
  71.     cin >> n;
  72.     vector <double> ans(n*n);
  73.     vector < vector <double> > a(n*n);
  74.     for(int i = 0; i < n; i++){
  75.         for(int j = 0; j < n; j++){
  76.             a[i*n+j].resize(n*n + 1, 0);
  77.             cin >> a[i*n + j][n*n];
  78.             for(int q = i-1; q <= i+1; q++)
  79.                 for(int p = j-1; p <= j+1; p++)
  80.                     if(q >= 0 && q < n && p >= 0 && p < n)
  81.                         a[i*n+j][q*n+p] = 1;
  82.  
  83.             // for(auto x: a[i*n + j])
  84.             //  cerr << x << " ";
  85.             // cerr << endl;               
  86.         }
  87.     }
  88.  
  89.     gauss(a, ans);
  90.  
  91.     for(int i = 0; i < n; i++){
  92.         for(int j = 0; j < n; j++){
  93.             int res = 0;
  94.             for(int q = i-1; q <= i+1; q++)
  95.                 for(int p = j-1; p <= j+1; p++)
  96.                     if(q >= 0 && q < n && p >= 0 && p < n)
  97.                         res+= ans[q*n + p];
  98.  
  99.             if(res != a[i*n + j][n*n])
  100.                 cerr << "WARNING! wrong ans in " << i << " " << j << ", except " << res << ", right" << a[i*n + j][n*n] << endl;
  101.         }
  102.     }
  103.  
  104.     for(int i = 0; i < n; i++){
  105.         for(int j = 0; j < n; j++){
  106.             cout << ans[i*n+j] << " ";
  107.         }
  108.         cout << endl;
  109.     }
  110.  
  111.     cerr << "end " << endl << endl;
  112. }
  113.  
  114. int main(){
  115.     ios_base::sync_with_stdio(0);
  116.     cin.tie(0);
  117.     cout.tie(0);
  118.  
  119.     int tests = 1;
  120.  
  121. #ifdef LOCAL
  122.     bool a;
  123.     a = freopen("in.data", "r", stdin);
  124.     a = freopen("out.data", "w", stdout);
  125.     cin >> tests;
  126. #endif
  127.  
  128.     while(tests--)
  129.         solve();
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement