Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ctime>
- using namespace std;
- #define pb push_back
- #define f first
- #define s second
- #define mp make_pair
- #define ll long long
- #define MAXN 200005
- #define INF 1000000009
- #define MOD 1000000007
- #define EPS 0.001
- int gauss (vector < vector< double > > a, vector<double> & ans) {
- int n = (int) a.size();
- int m = (int) a[0].size() - 1;
- unsigned int pre_time = clock();
- unsigned int start_time = pre_time;
- vector<int> where (m, -1);
- for (int col=0, row=0; col<m && row<n; ++col) {
- if((col+1) % 10 == 0){
- cerr << (long double)(col+1) / 100.0 << "% : ";
- cerr << (long double)(clock() - start_time) / 1000000.0 << " | " << (long double)(clock() - pre_time) / 1000000.0 << " sec\n";
- pre_time = clock();
- }
- int sel = row;
- for (int i=row; i<n; ++i)
- if (abs (a[i][col]) > abs (a[sel][col]))
- sel = i;
- if (abs (a[sel][col]) < EPS)
- continue;
- for (int i=col; i<=m; ++i)
- swap (a[sel][i], a[row][i]);
- where[col] = row;
- for (int i=0; i<n; ++i)
- if (i != row) {
- double c = a[i][col] / a[row][col];
- for (int j=col; j<=m; ++j)
- a[i][j] -= a[row][j] * c;
- }
- ++row;
- }
- cerr << "end col after " << (double)(clock() - start_time) / 1000000.0 << " sec" << endl;
- ans.assign (m, 0);
- for (int i=0; i<m; ++i)
- if (where[i] != -1)
- ans[i] = a[where[i]][m] / a[where[i]][i];
- for (int i=0; i<n; ++i) {
- double sum = 0;
- for (int j=0; j<m; ++j)
- sum += ans[j] * a[i][j];
- if (abs (sum - a[i][m]) > EPS)
- return 0;
- }
- for (int i=0; i<m; ++i)
- if (where[i] == -1)
- return INF;
- return 1;
- }
- void solve(){
- int n;
- cin >> n;
- vector <double> ans(n*n);
- vector < vector <double> > a(n*n);
- for(int i = 0; i < n; i++){
- for(int j = 0; j < n; j++){
- a[i*n+j].resize(n*n + 1, 0);
- cin >> a[i*n + j][n*n];
- for(int q = i-1; q <= i+1; q++)
- for(int p = j-1; p <= j+1; p++)
- if(q >= 0 && q < n && p >= 0 && p < n)
- a[i*n+j][q*n+p] = 1;
- // for(auto x: a[i*n + j])
- // cerr << x << " ";
- // cerr << endl;
- }
- }
- gauss(a, ans);
- for(int i = 0; i < n; i++){
- for(int j = 0; j < n; j++){
- int res = 0;
- for(int q = i-1; q <= i+1; q++)
- for(int p = j-1; p <= j+1; p++)
- if(q >= 0 && q < n && p >= 0 && p < n)
- res+= ans[q*n + p];
- if(res != a[i*n + j][n*n])
- cerr << "WARNING! wrong ans in " << i << " " << j << ", except " << res << ", right" << a[i*n + j][n*n] << endl;
- }
- }
- for(int i = 0; i < n; i++){
- for(int j = 0; j < n; j++){
- cout << ans[i*n+j] << " ";
- }
- cout << endl;
- }
- cerr << "end " << endl << endl;
- }
- int main(){
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int tests = 1;
- #ifdef LOCAL
- bool a;
- a = freopen("in.data", "r", stdin);
- a = freopen("out.data", "w", stdout);
- cin >> tests;
- #endif
- while(tests--)
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement