gcj2020/qr/qr1.cc at master · sleinen/gcj2020 · 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
/*
 qr1.c

 Date Created: Sat Apr  4 12:20:38 2020
 Author:       Simon Leinen  <simon.leinen@switch.ch>
 */
#include <iostream>
#include <cstdint>

using namespace std;

const unsigned maxN = 100;

int
main () {
  unsigned T, N;
  cin >> T;
  for (unsigned caseno = 1; caseno <= T; ++caseno) {
    unsigned A[maxN][maxN];
    uint8_t dup_rows = 0;
    uint8_t dup_cols = 0;
    cin >> N;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        cin >> A[i][j];
      }
    }
    unsigned trace = 0;
    for (int a = 0; a < N; a++) {
      trace += A[a][a];
      uint8_t row_seen[maxN], this_row_dup = 0;
      uint8_t col_seen[maxN], this_col_dup = 0;
      for (int b = 0; b < N; b++) {
        row_seen[b] = col_seen[b] = 0;
      }
      for (int b = 0; b < N; b++) {
        unsigned c1 = A[a][b] - 1;
        unsigned c2 = A[b][a] - 1;
        if (row_seen[c1]) {
          if (!this_row_dup) { this_row_dup = 1; dup_rows++; };
        } else {
          row_seen[c1] = 1;
        }
        if (col_seen[c2]) {
          if (!this_col_dup) { this_col_dup = 1; dup_cols++; };
        } else {
          col_seen[c2] = 1;
        }
      }
    }
    cout << "Case #" << caseno << ": " << trace << " " << (int) dup_rows << " " << (int) dup_cols;
    cout << "\n";
  }
}