Solution Notes (Albert Gu): Consider two cows labeled A and B. Suppose that in the original ordering, A came before B. Notice that in the five photographs, neither A nor B moved in at least three of them (that is, A and B must still be in the correct relative order in at least three of the photographs). Given these five photographs, we can just compare the number of times A came before B; if it is three or more, then A is before B in the original ordering, otherwise B is before A in the original ordering. This provides us with a fast comparison function between any two cows. Now all that is left is sorting all the cows using this comparator.

Here is Mark Gordon's short solution:


#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>

using namespace std;

#define MAXN 20000

int A[MAXN];
map<int, int> pos[5];

bool cmp(int a, int b) {
  int f = 0;
  for(int i = 0; i < 5; i++) {
    f += pos[i][a] < pos[i][b];
  }
  return f > 2;
}

int main() {
  freopen("photo.in", "r", stdin);
  freopen("photo.out", "w", stdout);
  int N; cin >> N;
  for(int i = 0; i < 5; i++) {
    for(int j = 0; j < N; j++) {
      int x; cin >> x;
      pos[i][x] = j;
      A[j] = x;
    }
  }
  sort(A, A + N, cmp);
  for(int i = 0; i < N; i++) {
    cout << A[i] << '\n';
  }
}