Lucky-SAT

#include <iostream>
#include <algorithm>

using namespace std;
int t[10001], dep[100], only_dep[100];
bool result[10001], sat[100];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int r[n][7];
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 7; ++j) {
      cin >> r[i][j];
      if (r[i][j] > 0) t[r[i][j]]++;
      else t[-r[i][j]]--;
    }
  }
  int satleft = n;
  for (int i = 1; i <= m; ++i) {
    result[i] = t[i] >= 0;
    for (int j = 0; j < n; ++j) {
      if (sat[j]) continue;
      bool remove = false;
      for (int k = 0; k < 7; ++k) {
        if (r[j][k] == (result[i] ? i : -i)) {
          remove = true;
          break;
        }
      }
      if (remove) {
        for (int k = 0; k < 7; ++k) {
          if (r[j][k] > 0) t[r[j][k]]--;
          else t[-r[j][k]]++;
        }
        sat[j] = 1;
        satleft--;
      }
    }
  }
  if (satleft != 0) {
    cout << "UNSAT\n";
  } else {
    cout << "SAT\n";
    for (int i = 1; i <= m; ++i) cout << result[i];
    cout << endl;
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED