BOJ 26977 - Reverse Engineering

BOJ 26977 - Reverse Engineering

Greedy + Ad hoc 문제이다.

일단 input이 같은데 output이 다른것이 있다면 LIE를 출력해준다.

그렇지않다면 계속 같은 column 을 보면서 예를 들어, 지워지지 않은 input 중에 0 인 것들이 output이 모두 같다면 해당 if 문이 있어서 그걸 바로 0 으로 return 해준 것으로 생각해줄 수 있으므로 모두 없앤다.

1도 마찬가지로 진행한다.

void solve() {
   int n, m;
   cin >> n >> m;
   vector<pair<string, int>> a(m);
   for (auto &[i, o]: a) cin >> i >> o;
   for (int i = 0; i < m; i++)
      for (int j = i + 1; j < m; j++)
         if (a[i].fi == a[j].fi && a[i].se != a[j].se) {
            cout << "LIE\n";
            return;
         }

   vi erased(m);
   while (cntt(erased, 1) < m) {
      bool find = 0;
      for (int i = 0; i < n; i++) {
         // <그룹, output>
         vvi can(2, vi(2));

         for (int j = 0; j < m; j++) {
            if (erased[j]) continue;
            can[a[j].fi[i] - '0'][a[j].se] = 1;
         }

         for (int g = 0; g < 2; g++) {
            if (can[g][0] != can[g][1]) {
               find = 1;
               int win = can[g][0] == 1 ? 0 : 1;
               for (int j = 0; j < m; j++)
                  if (a[j].fi[i] - '0' == g && a[j].se == win)
                     erased[j] = 1;
               goto out;
            }
         }
      }

      out:;
      if (!find) {
         cout << "LIE\n";
         return;
      }
   }
   cout << "OK\n";

}