Cow Photography

Farmer John'un çiftliğinde N ineği ve her birinin farklı id numarası vardır. Farmer John tüm ineklerin 5 kere fotoğrafını çekecektir. İlk başta bu N inek orijinal sıralarındadırlar. Farmer John'un her fotoğraf çekişinde bir grup inek(boş grup olabilir) istediği gibi yerini değiştirebilir. Bir inek 2 grupta olamaz yani her ineğin maksimum 1 kere yer değiştirme hakkı vardır. Sizden istenilen bu N inekin orijinal sırası.

Input Format
İlk satırda N: inek sayısı
Sonraki 5*N satır: Her fotoğraf için her ineğin id'sini gösteren N satır

Output Format
N satırda ineklerin orijinal sırası.

Constraints
1 <= N <= 20,000
0 <= id <= 1,000,000,000

Input

5

10

20

30

40

50

20

10

30

40

50

30

10

20

40

50

40

10

20

30

50

50

10

20

30

40

Output

10

20

30

40

50

______________________________________

Link

Soru, Test Data ve Solutions : http://usaco.org/index.php?page=dec11problems
______________________________________

Çözüm

Bu soru aslında her ne kadar basit olsa da çözüm yolu ilginçtir ve sorting ile çözülmektedir.

1 <= t <= 5 , 1 <= x,y <= N olmak üzere
g(t,x,y): t. fotoğrafta x.ineğin y.ineğin önünde olup olmadığını göstersin. Eğer x öndeyse 1, y öndeyse değerimiz 0 olsun.
f(x,y): g(1,x,y)+g(2,x,y)+g(3,x,y)+g(4,x,y)+g(5,x,y) toplamı olsun.

Şimdi söyle düşünelim...
x, y'nin önünde olsun. f(x,y) en kötü ihtimalde 3 olur. x, y'nin arkasına ve bundan ayrı bir fotoğrafta y, x'in önüne geçerse toplamda y 2 kere öne geçmiş olur ve x, y'nin 3 kere önünde kalmış olur.
x, y'nin arkasında olsun. f(x,y) en iyi ihtimalde 2 olur. Bu sefer x, y'nin önüne ve bundan ayrı bir fotoğrafta y, x'in arkasına geçerse x, y'nin toplamda 2 kere öne geçmiş olur.

Sonuç olarak f(x,y) >= 3 ise x, y'nin önündedir.

Bundan sonra her inek için bir struct yapısı oluşturup bir sort çekersek kolayca orijinal sırayı hesaplamış oluruz.
______________________________________

Kodum

#include <algorithm>
#include <stdio.h>
#include <vector>
#include <map>
#define  maxn    20003
#define  pb         push_back
using     namespace std;

struct data
{
  int val;
  vector<int>v;
}ar[maxn];

int n,m;
map<int,int>hash;

bool comp(data a , data b)
{
  int cnt=0;
  for(int i=0 ; i<5 ; i++)
    if(a.v[i]<b.v[i])
      cnt++;
  return (cnt>=3);
}

int main()
{
  scanf("%d",&n);
  for(int i=1 ; i<=5 ; i++)
    for(int j=1 ; j<=n ; j++)
    {
 int x;
 scanf("%d",&x);
 if(i==1 && !hash[x]) { hash[x]=++m; ar[m].val=x; }
 (ar[hash[x]].v).pb(j);
    }
  sort(ar+1,ar+n+1,comp);
  for(int i=1 ; i<=n ; i++)
    printf("%d\n",ar[i].val);
  return 0;
}