BOJ 27067 - 데이터 순서 복원

BOJ 27067 - 데이터 순서 복원

어딘가에서 본듯한 문제인데, 특별한 comparision을 가지고 정렬을 하는 문제이다.

어떤 $i,j$ 가 존재하는데 $a$에선 $i$가 $j$보다 먼저 나왔고 $b$에선 $i$가 $j$보다 먼저나왔고 $c$에선 $i$가 $j$보다 늦게나왔다고 하자.

이 경우 원래 배열에서도 항상 $i$가 $j$보다 먼저 나와야 함을 가지고 정렬한다.

왜냐면 $i - j$ 순으로 되어있는데 $j$가 $i$ 앞으로 갈 수 있는 횟수는 최대 $1$번이기 때문이다.

void solve() {  
   int n;  
   cin >> n;  
   vi a(n), b(n), c(n);  
   fv(a)  
   fv(b)  
   fv(c);  
   vi ans;  
   for (int i = 1; i <= n; i++) ans.pb(i);  
   auto idx_of = [&](vi &a, int x) {  
      for (int i = 0; i < n; i++) if (a[i] == x) return i;  
   };  
   auto cmp = [&](int i, int j) {  
      int amin = 0;  
      amin += idx_of(a, i) < idx_of(a, j) ? 1 : 0;  
      amin += idx_of(b, i) < idx_of(b, j) ? 1 : 0;  
      amin += idx_of(c, i) < idx_of(c, j) ? 1 : 0;  
      return amin >= 2;  
   };  
   sort(all(ans), cmp);  
   for (int i: ans) cout << i << ' ';  
}