algorithms/solutions/code-jam/2020-QR-indicium-TLE.cpp at master · brpapa/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
   brute force > recursive backtracking
   difficulty: easy
   date: 04/Apr/2020
   problem: generate M, where M[i][j] is any value in [1 .. N] (2 <= N <= 5), but without repeting a value in same line or column, and with the sum of the main diagonal equal to K
   by: @brpapa
*/
#include <iostream>
#define ll long long
#define MAX_N 55
#define bitIsOn(S, i) (S & (1 << i))
#define setBit(S, i) (S |= (1 << i))
#define clearBit(S, i) (S &= ~(1 << i))
using namespace std;

int M[MAX_N][MAX_N];
int N, K;

ll usedOnRow[MAX_N]; // usedOnRow[r] = bitmask indicando se num já foi usado na linha r
ll usedOnCol[MAX_N]; // usedOnRow[r] = bitmask indicando se num já foi usado na coluna c
int sumDiagonal;

bool hasSolution;

void bt(int i) {
   int r = i/N, c = i%N;
   // define M[r][c] com algum num possivel

   if (hasSolution) return;

   if (i == N*N) {
      hasSolution = true;

      cout << "POSSIBLE" << endl;
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++)
            cout << M[i][j] << " ";
         cout << endl;
      }
      return;
   }
   else {
      for (int num = 1; num <= N; num++) {
         // se num é válido em M[r][c]
         if (!bitIsOn(usedOnRow[r], num)
          && !bitIsOn(usedOnCol[c], num)
          && (r != c || sumDiagonal+num <= K)
          && (i != N*N-1 || sumDiagonal+num == K)) {

            M[r][c] = num;

            if (r == c) sumDiagonal += num;
            setBit(usedOnRow[r], num), setBit(usedOnCol[c], num);

            bt(i+1);

            if (r == c) sumDiagonal -= num;
            clearBit(usedOnRow[r], num), clearBit(usedOnCol[c], num);
         }
      }
   }
}

int main() {
   int t = 1, T; cin >> T;
   while (T--) {
      cin >> N >> K;

      hasSolution = false;
      sumDiagonal = 0;
      for (int i = 0; i < N; i++) usedOnRow[i] = 0, usedOnCol[i] = 0;

      printf("Case #%d: ", t++);
      bt(0);
      if (!hasSolution) cout << "IMPOSSIBLE" << endl;
   }
   return 0;
}