Advertisement
DylanHarris

ALADDING

Feb 8th, 2020
631
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.60 KB | None | 0 0
  1. ///....DH....///
  2. #include <bits/stdc++.h>
  3. #define task                "ALADDIN"
  4. #define fi(a)               freopen(a, "r", stdin)
  5. #define fo(a)               freopen(a, "w", stdout)
  6.  
  7. #define pii                 pair<int, int>
  8. #define ft                  first
  9. #define sd                  second
  10. #define mp                  make_pair
  11.  
  12. #define pb                  push_back
  13. #define pf                  push_front
  14. #define popb                pop_back
  15. #define popf                pop_front
  16.  
  17. #define reset(a, x)         memset(a, x, sizeof(a))
  18. #define For(i, s, n, m)     for(int i = s; i <= n; i += m)
  19. #define Ford(i, s, n, m)    for(int i = s; i >= n; i -= m)
  20.  
  21. using namespace std;
  22.  
  23. template <typename R, typename D> inline void Min(R &a, D b) {
  24.     if(a>b)
  25.         a=b;
  26. }
  27. template <typename D, typename R> inline void Max(D &a, R b) {
  28.     if(a<b)
  29.         a=b;
  30. }
  31.  
  32. /** MOD **/                 const long long mod = 1e9 + 7;
  33. /** size of array **/       const int maxn = 205;
  34.  
  35. int a[maxn][maxn], b[maxn][maxn], n;
  36. bool ok;
  37.  
  38. void backtrack(int x) {
  39.     if(x > n) {
  40.         for(int i = 1; i <= n; i++) {
  41.             for(int j = 1; j <= n; j++)
  42.                 cout << a[i][j] << " ";
  43.             cout << "\n";
  44.         }
  45.         ok = true;
  46.         return ;
  47.     }
  48.     for(int u = 0; u <= 1; u++)
  49.         for(int v = 0; v <= 1; v++) {
  50.             bool ne = true;
  51.             a[1][x] = u;
  52.             a[x][1] = v;
  53.             for(int i = 2; i < x; i++) {
  54.                 a[x][i] = b[x - 1][i - 1] - a[x - 1][i - 1] - a[x][i - 1] - a[x - 1][i];
  55.                 if(a[x][i] < 0 || a[x][i] > 1) {
  56.                     ne = false;
  57.                     a[x][i] = 0;
  58.                     break ;
  59.                 }
  60.             }
  61.             if(ne == true) {
  62.                 for(int i = 2; i <= x; i++) {
  63.                     a[i][x] = b[i - 1][x - 1] - a[i - 1][x - 1] - a[i][x - 1] - a[i - 1][x];
  64.                     if(a[i][x] < 0 || a[i][x] > 1) {
  65.                         ne = false;
  66.                         a[i][x] = 0;
  67.                         break ;
  68.                     }
  69.                 }
  70.             }
  71.             if(ne == true)
  72.                 backtrack(x + 1);
  73.             if(ok == true)
  74.                 return ;
  75.         }
  76. }
  77. main() {
  78.     ios_base::sync_with_stdio(false);
  79.     cin.tie(0), cout.tie(0);
  80.     cin >> n;
  81.     for(int i = 1; i < n; i++)
  82.         for(int j = 1; j < n; j++)
  83.             cin >> b[i][j];
  84.  
  85.     backtrack(2);
  86.     if(ok == false) {
  87.         memset(a, 0, sizeof(a));
  88.         a[1][1] = 1;
  89.         backtrack(2);
  90.     }
  91.     if(ok == false)
  92.         cout << "No solution";
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement