# 台北市104 學年度資訊學科能力競賽 pC. Underdog ( 田忌賽馬 )

```#include <bits/stdc++.h>
using namespace std;

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int, int > pii;
typedef vector< pii > vp;

int K, N;
vi S; // team id to rank
vi rS; // rank to team id
vvi P, U, L;

void init(){
cin >> K >> N;
S = rS = vi( N );
P = U = L = vvi( N, vi( 2 * K + 1 ) );
for( int i = 0; i < N; ++i ){
cin >> S[ i ],
--S[ i ],
rS[ S[ i ] ] = i;
for( int j = 0; j < 2 * K + 1; ++j )
cin >> P[ i ][ j ];
for( int j = 0; j < 2 * K + 1; ++j )
cin >> U[ i ][ j ];
for( int j = 0; j < 2 * K + 1; ++j )
cin >> L[ i ][ j ];
}
}

int win( vi a, vi b, int rank_a, int rank_b ){
for( int i = 0; i < a.size() / 2; ++i )
a.insert( a.begin(), a.back() ),
a.pop_back();
int win_cnt = 0;
for( int i = 0; i < a.size(); ++i )
if( a[ i ] > b[ i ] or ( a[ i ] == b[ i ] and rank_a < rank_b ) )
++win_cnt;
return win_cnt >= K + 1;
}

void solve(){
for( int i = N - 1; i >= 0; --i ){
int win_all = 1;
for( int j = 0; j < N; ++j )
if( rS[ i ] != j )
if( not win( P[ rS[ i ] ], P[ j ], i, S[ j ] ) ){
win_all = 0;
break;
}
if( win_all ){
cout << rS[ i ] + 1 << " ";
break;
}
}
for( int i = N - 1; i >= 0; --i ){
int win_all = 1;
for( int j = 0; j < N; ++j )
if( rS[ i ] != j )
if( not win( U[ rS[ i ] ], L[ j ], i, S[ j ] ) ){
win_all = 0;
break;
}
if( win_all ){
cout << rS[ i ] + 1 << endl;
break;
}
}
}

signed main(){
ios::sync_with_stdio( false );
init();
solve();
return 0;
}
```