fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(v) (v).begin(), (v).end()
  4.  
  5. vector<int> sumrow(5), sumcol(5);
  6. bitset<32> visited(0);
  7. vector<int> idxRow, idxCol;
  8. int result[7][7];
  9. int ans[7][7];
  10.  
  11. void sort_idx(vector<int> &idx, vector<int> &v)
  12. {
  13.     idx.resize(v.size());
  14.     iota(all(idx), 0);
  15.     stable_sort(all(idx), [&](const int &i1, const int &i2) { return v[i1] < v[i2]; });
  16. }
  17.  
  18. inline void printResult()
  19. {
  20.     for(int i = 0; i < 5; i++)
  21.     {
  22.         for(int j = 0; j < 5; j++)
  23.         {
  24.             printf("%d ", ans[i][j]);
  25.         }
  26.         printf("\n");
  27.     }
  28. }
  29. bool stop = false;
  30. void solution(int k)
  31. {
  32.     if(stop) return;
  33.     if(k == 25)
  34.     {
  35.         for(int i = 0; i < 5; i++)
  36.         {
  37.             for(int j = 0; j < 5; j++)
  38.             {
  39.                 int oldX = idxRow[i];
  40.                 int oldY = idxCol[j];
  41.                 ans[oldX][oldY] = result[i][j];
  42.             }
  43.         }
  44.         printResult();
  45.         stop = true;
  46.         return;
  47.     }
  48.  
  49.     int x = k / 5;
  50.     int y = k % 5;
  51.  
  52.     int L = 1, R = 25;
  53.     int c1 = sumrow[x];
  54.     int c2 = sumcol[y];
  55.     if(y == 4) L = R = c1;
  56.     else if(x == 4)
  57.         L = R = c2;
  58.     else
  59.     {
  60.         int a1 = 0, a2 = 0;
  61.         int b1 = 0, b2 = 0;
  62.         int maxx = max(5 - (x + 1), 5 - (y + 1));
  63.         for(int i = 25, cnt1 = 0, cnt2 = 0; i >= 1 && cnt1 < maxx && cnt2 < maxx; --i)
  64.         {
  65.             if(!visited.test(i))
  66.             {
  67.                 if(cnt1 < 5 - (x + 1))
  68.                 {
  69.                     b2 += i;
  70.                     ++cnt1;
  71.                 }
  72.                 if(cnt2 < 5 - (y + 1))
  73.                 {
  74.                     a2 += i;
  75.                     ++cnt2;
  76.                 }
  77.             }
  78.         }
  79.         for(int i = 1, cnt1 = 0, cnt2 = 0; i <= 25 && cnt1 < maxx && cnt2 < maxx; ++i)
  80.         {
  81.             if(!visited.test(i))
  82.             {
  83.                 if(cnt1 < 5 - (x + 1))
  84.                 {
  85.                     b1 += i;
  86.                     ++cnt1;
  87.                 }
  88.                 if(cnt2 < 5 - (y + 1))
  89.                 {
  90.                     a1 += i;
  91.                     ++cnt2;
  92.                 }
  93.             }
  94.         }
  95.         L = max({1, c1 - a2, c2 - b2});
  96.         R = min({25, c1 - a1, c2 - b1});
  97.     }
  98.     if(L > 25 || R < 1 || L > R) return;
  99.  
  100.     for(int i = L; i <= R; ++i)
  101.     {
  102.         if(!visited.test(i))
  103.         {
  104.             visited.set(i);
  105.             sumcol[y] -= i;
  106.             sumrow[x] -= i;
  107.             result[x][y] = i;
  108.  
  109.             solution(k + 1);
  110.  
  111.             if(stop) return;
  112.             visited.reset(i);
  113.             sumcol[y] += i;
  114.             sumrow[x] += i;
  115.         }
  116.     }
  117. }
  118.  
  119. int main()
  120. {
  121.     ios::sync_with_stdio(false);
  122.     cin.tie(nullptr);
  123.     cout.tie(nullptr);
  124.  
  125.     for(int i = 0; i < 5; i++) scanf("%d", &sumrow[i]);
  126.     for(int i = 0; i < 5; i++) scanf("%d", &sumcol[i]);
  127.  
  128.     sort_idx(idxRow, sumrow);
  129.     sort_idx(idxCol, sumcol);
  130.  
  131.     sort(all(sumrow));
  132.     sort(all(sumcol));
  133.  
  134.     solution(0);
  135.  
  136.     return 0;
  137. }
Success #stdin #stdout 0s 5676KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/QrBNuH
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!