Problem:


Problem J: Usaneko Matrix

うさぎとねこが勝負をしている. ルールは以下の通りである.

まず2 匹はそれぞれn 行n 列の正方形状にn2 個の整数を紙に書き, トランプを1 枚ずつ引く. 次に, 1 から 1 000 000 までの数が1 つずつ書かれた1 000 000 枚のカードを2 匹でシャッフルし, これを1 枚ずつ交互に引いていく. 2 匹はカードが引かれるたび, カードと同じ数が自分の紙に書かれていたらそれに印をつける. 「印がついたn 個の数の組であって, 一直線上に並んでいるもの」の個数が, はじめに引いたトランプの数以上になることを勝利条件とする.

与えられたm 枚目のカードまでで, うさぎとねこのどちらが勝つか答えよ. ただし勝敗は, あるカードが引かれて印をつけ終わった段階で2 匹のうち片方のみが勝利条件をみたしたときに決まるものとし, それ以外の場合は引き分けとする. いずれかが勝利条件をみたした後でもカードが引かれることはあるが, これは勝敗に影響しない.

Input

1 行目：“n u v m” (正方形のサイズ, うさぎのトランプの数, ねこのトランプの数, 引かれるカードの枚数) 2-(N + 1) 行目：うさぎが紙に書くn2 個の数(N + 2)-(2N + 1) 行目：ねこが紙に書くn2 個の数(2N + 2)-(2N +M + 1) 行目：引かれるm 枚のカード

1 ≤ n ≤ 500

1 ≤ u, v ≤ 13

1 ≤ m ≤ 100 000

1 ≤ (書かれる数) ≤ 1 000 000

うさぎが紙に書くn2 個の数, ねこが紙に書くn2 個の数, 引かれるm 枚のカードに書かれた数はそれぞれの中で異なる.

Output

うさぎが勝つ場合には”USAGI”を, ねこが勝つ場合には”NEKO”を, 引き分けならば”DRAW”, それぞれ
一行に出力せよ.

Sample Input 1

3 2 2 10
1 2 3
4 5 6
7 8 9
1 2 3
6 5 4
7 8 9
11
4
7
5
10
9
2
1
3
8

Sample Output 1

USAGI

Sample Input 2

3 2 1 10
1 2 3
4 5 6
7 8 9
1 2 3
6 5 4
7 8 9
11
4
7
5
10
9
2
1
3
8

Sample Output 2

DRAW



Sample input:
3 2 2 10
1 2 3
4 5 6
7 8 9
1 2 3
6 5 4
7 8 9
11
4
7
5
10
9
2
1
3
8


Sample output:
USAGI

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,u,v,m = LI()
    ud = {}
    for i in range(n):
        t = LI()
        for j in range(n):
            ud[t[j]] = (i,j)
    vd = {}
    for i in range(n):
        t = LI()
        for j in range(n):
            vd[t[j]] = (i,j)

    ma = [I() for _ in range(m)]
    ut = collections.defaultdict(bool)
    vt = collections.defaultdict(bool)
    un = 0
    vn = 0
    for t in ma:
        if t in ud:
            ut[ud[t]] = True
            ui,uj = ud[t]
            for di,dj in ddn[:4]:
                k = 1
                for i in range(1, n):
                    if not ut[(ui+di*i, uj+dj*i)]:
                        break
                    k += 1
                for i in range(-1, -n, -1):
                    if not ut[(ui+di*i, uj+dj*i)]:
                        break
                    k += 1
                if k >= n:
                    un += 1

        if t in vd:
            vt[vd[t]] = True
            vi,vj = vd[t]
            for di,dj in ddn[:4]:
                k = 1
                for i in range(1, n):
                    if not vt[(vi+di*i, vj+dj*i)]:
                        break
                    k += 1
                for i in range(-1, -n, -1):
                    if not vt[(vi+di*i, vj+dj*i)]:
                        break
                    k += 1
                if k >= n:
                    vn += 1

        if un >= u and vn < v:
            return 'USAGI'
        if vn >= v and un < u:
            return 'NEKO'
        if un >= u and vn >= v:
            break

    return 'DRAW'



print(main())

Submission status: Wrong Answer

Solution code:
n, u, v, m = map(int, input().split())
usa_mat = [list(map(int, input().split())) for _ in range(n)]
nek_mat = [list(map(int, input().split())) for _ in range(n)]
usa_dic = {}
nek_dic = {}
for y in range(n):
  for x in range(n):
    usa_dic[usa_mat[y][x]] = (x, y)
    nek_dic[nek_mat[y][x]] = (x, y)

usa_count = [0] * (2 * n + 2)
nek_count = [0] * (2 * n + 2)

flag = 0
usa_point = 0
nek_point = 0
for _ in range(m):
  a = int(input())
  if flag:
    continue
  
  if a in usa_dic:
    ux, uy = usa_dic[a]
    usa_count[ux] += 1
    if usa_count[ux] == n:
      usa_point += 1
    usa_count[uy + n] += 1
    if usa_count[uy + n] == n:
      usa_point += 1
    if ux + uy == n:
      usa_count[-1] += 1
      if usa_count[-1] == n:
        usa_point += 1
    if ux == uy:
      usa_count[-2] += 1
      if usa_count[-2] == n:
        usa_point += 1
  
  if a in nek_dic:
    nx, ny = nek_dic[a]
    nek_count[nx] += 1
    if nek_count[nx] == n:
      nek_point += 1
    nek_count[ny + n] += 1
    if nek_count[ny + n] == n:
      nek_point += 1
    if nx + ny == n:
      nek_count[-1] += 1
      if nek_count[-1] == n:
        nek_point += 1
    if nx == ny:
      nek_count[-2] += 1
      if nek_count[-2] == n:
        nek_point += 1

  if usa_point >= u and nek_point >= v:
    flag = 1
  elif usa_point >= u:
    flag = 2
  elif nek_point >= v:
    flag = 3

if flag == 2:
  print("USAGI")
elif flag == 3:
  print("NEKO")
else:
  print("DRAW")

Submission status: Wrong Answer

Solution code:
n, u, v, m = map(int, input().split())
usa_mat = [list(map(int, input().split())) for _ in range(n)]
nek_mat = [list(map(int, input().split())) for _ in range(n)]
usa_dic = {}
nek_dic = {}
for y in range(n):
  for x in range(n):
    usa_dic[usa_mat[y][x]] = (x, y)
    nek_dic[nek_mat[y][x]] = (x, y)

usa_count = [0] * (2 * n + 2)
nek_count = [0] * (2 * n + 2)

flag = 0
usa_point = 0
nek_point = 0
for _ in range(m):
  a = int(input())
  if flag:
    continue
  
  if a in usa_dic:
    ux, uy = usa_dic[a]
    usa_count[ux] += 1
    if usa_count[ux] == n:
      usa_point += 1
    usa_count[uy + n] += 1
    if usa_count[uy + n] == n:
      usa_point += 1
    if ux + uy == n:
      usa_count[-1] += 1
      if usa_count[-1] == n:
        usa_point += 1
    if ux == uy:
      usa_count[-2] += 1
      if usa_count[-2] == n:
        usa_point += 1
  
  if a in nek_dic:
    nx, ny = nek_dic[a]
    nek_count[nx] += 1
    if nek_count[nx] == n:
      nek_point += 1
    nek_count[ny + n] += 1
    if nek_count[ny + n] == n:
      nek_point += 1
    if nx + ny == n:
      nek_count[-1] += 1
      if nek_count[-1] == n:
        nek_point += 1
    if nx == ny:
      nek_count[-2] += 1
      if nek_count[-2] == n:
        nek_point += 1
  
  if n == 1:
    usa_point = min(usa_point, 1)
    nek_point = min(nek_point, 1)

  if usa_point >= u and nek_point >= v:
    flag = 1
  elif usa_point >= u:
    flag = 2
  elif nek_point >= v:
    flag = 3
if flag == 2:
  print("USAGI")
elif flag == 3:
  print("NEKO")
else:
  print("DRAW")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n,u,v,m = map(int, raw_input().split())
U=defaultdict(tuple)
N=defaultdict(tuple)
for i in range(n):
    l=map(int, raw_input().split())
    for j in range(n):
        U[ l[j] ] = (i,j)
for i in range(n):
    l=map(int, raw_input().split())
    for j in range(n):
        N[ l[j] ] = (i,j)
Uw = [[0 for i in range(n)],[0 for i in range(n)],[0,0],0]
Nw = [[0 for i in range(n)],[0 for i in range(n)],[0,0],0]
for x in range(m):
    q=int(raw_input())
    for A in  [[U,Uw],[N,Nw]]:
        if A[0][q]!=():
            qi,qj = A[0][q]
            A[1][0][qi] += 1
            A[1][1][qj] += 1
            if qi==qj:
                A[1][2][0]+=1
            if qi==n-qj-1:
                A[1][2][1]+=1
            A[1][3] += A[1][0][qi]==n
            A[1][3] += A[1][1][qj]==n
            A[1][3] += A[1][2][0] ==n
            A[1][3] += A[1][2][1] ==n

    if Uw[3]>=u and Nw[3]<v:
        ans="USAGI"
        break
    if Nw[3]>=v and Uw[3]<u:
        ans="NEKO"
        break
    if Nw[3]>=v and Uw[3]>=u:
        ans="DRAW"
        break
else:
    ans="DRAW"
print ans

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n,u,v,m = map(int, raw_input().split())
U=defaultdict(tuple)
N=defaultdict(tuple)
for i in range(n):
    l=map(int, raw_input().split())
    for j in range(n):
        U[ l[j] ] = (i,j)
for i in range(n):
    l=map(int, raw_input().split())
    for j in range(n):
        N[ l[j] ] = (i,j)
Uw = [[0 for i in range(n)],[0 for i in range(n)],[0,0],0]
Nw = [[0 for i in range(n)],[0 for i in range(n)],[0,0],0]
if n==1:
    Uw[3]-=3
    Nw[3]-=3
for x in range(m):
    q=int(raw_input())
    for A in  [[U,Uw],[N,Nw]]:
        if A[0][q]!=():
            qi,qj = A[0][q]
            A[1][0][qi] += 1
            A[1][1][qj] += 1
            if qi==qj:
                A[1][2][0]+=1
            if qi==n-qj-1:
                A[1][2][1]+=1
            A[1][3] += A[1][0][qi]==n
            A[1][3] += A[1][1][qj]==n
            A[1][3] += A[1][2][0] ==n
            A[1][3] += A[1][2][1] ==n

    if Uw[3]>=u and Nw[3]<v:
        ans="USAGI"
        break
    if Nw[3]>=v and Uw[3]<u:
        ans="NEKO"
        break
    if Nw[3]>=v and Uw[3]>=u:
        ans="DRAW"
        break
else:
    ans="DRAW"
print ans

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

n, u, v, m = map(int, raw_input().split())

m1 = {}
m2 = {}

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        l = [i, n + j]
        if i == j:
            l.append(2 * n)
        if i + j == n - 1:
            l.append(2 * n + 1)
        m1[lst_[j]] = l

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        l = [i, n + j]
        if i == j:
            l.append(2 * n)
        if i + j == n - 1:
            l.append(2 * n + 1)
        m2[lst_[j]] = l

mu = {}
mv = {}

for loop in range(m):
    num = input()
    if num in m1:
        l = m1[num]
        for p in l:
            if not p in mu:
                mu[p] = 1
            else:
                mu[p] += 1
            if mu[p] == n:
                u -= 1
    
    if num in m2:
        l = m2[num]
        for p in l:
            if not p in mv:
                mv[p] = 1
            else:
                mv[p] += 1
            if mv[p] == n:
                v -= 1
    if u == 0 or v == 0:
        if u < v:
            print "USAGI"
        elif u > v:
            print "NEKO"
        else:
            print "DRAW"
        exit()

print "DRAW"

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

n, u, v, m = map(int, raw_input().split())

m1 = {}
m2 = {}

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        l = [i, n + j]
        if i == j:
            l.append(2 * n)
        if i + j == n - 1:
            l.append(2 * n + 1)
        m1[lst_[j]] = l

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        l = [i, n + j]
        if i == j:
            l.append(2 * n)
        if i + j == n - 1:
            l.append(2 * n + 1)
        m2[lst_[j]] = l

mu = {}
mv = {}

for loop in range(m):
    num = input()
    if num in m1:
        l = m1[num]
        for p in l:
            if not p in mu:
                mu[p] = 1
            else:
                mu[p] += 1
            if mu[p] == n:
                u -= 1
    
    if num in m2:
        l = m2[num]
        for p in l:
            if not p in mv:
                mv[p] = 1
            else:
                mv[p] += 1
            if mv[p] == n:
                v -= 1
    if u <= 0 or v <= 0:
        if u < v:
            print "USAGI"
        elif u > v:
            print "NEKO"
        else:
            print "DRAW"
        exit()

print "DRAW"

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

n, u, v, m = map(int, raw_input().split())

m1 = {}
m2 = {}

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        l = [i, n + j]
        if not n == 1:
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m1[lst_[j]] = l

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        l = [i, n + j]
        if not n == 1:
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m2[lst_[j]] = l

mu = {}
mv = {}

for loop in range(m):
    num = input()
    if num in m1:
        l = m1[num]
        for p in l:
            if not p in mu:
                mu[p] = 1
            else:
                mu[p] += 1
            if mu[p] == n:
                u -= 1
    
    if num in m2:
        l = m2[num]
        for p in l:
            if not p in mv:
                mv[p] = 1
            else:
                mv[p] += 1
            if mv[p] == n:
                v -= 1
    if u <= 0 or v <= 0:
        if u < v:
            print "USAGI"
        elif u > v:
            print "NEKO"
        else:
            print "DRAW"
        exit()

print "DRAW"

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

n, u, v, m = map(int, raw_input().split())

m1 = {}
m2 = {}

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        l = [i, n + j]
        if not n == 1:
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m1[lst_[j]] = l

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        l = [i, n + j]
        if not n == 1:
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m2[lst_[j]] = l

mu = {}
mv = {}

for loop in range(m):
    num = input()
    if num in m1:
        l = m1[num]
        for p in l:
            if not p in mu:
                mu[p] = 1
            else:
                mu[p] += 1
            if mu[p] == n:
                u -= 1
    
    if num in m2:
        l = m2[num]
        for p in l:
            if not p in mv:
                mv[p] = 1
            else:
                mv[p] += 1
            if mv[p] == n:
                v -= 1
    if u <= 0 or v <= 0:
        if v > 0:
            print "USAGI"
        elif u > 0:
            print "NEKO"
        else:
            print "DRAW"
        exit()

print "DRAW"

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

n, u, v, m = map(int, raw_input().split())

m1 = {}
m2 = {}

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        if n == 1:
            l = [0]
        else:
            l = [i, n + j]
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m1[lst_[j]] = l

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        if n == 1:
            l = [0]
        else:
            l = [i, n + j]
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m2[lst_[j]] = l

mu = {}
mv = {}

for loop in range(m):
    num = input()
    if num in m1:
        l = m1[num]
        for p in l:
            if not p in mu:
                mu[p] = 1
            else:
                mu[p] += 1
            if mu[p] == n:
                u -= 1
    
    if num in m2:
        l = m2[num]
        for p in l:
            if not p in mv:
                mv[p] = 1
            else:
                mv[p] += 1
            if mv[p] == n:
                v -= 1
    print u, v
    if u <= 0 or v <= 0:
        if v > 0:
            print "USAGI"
        elif u > 0:
            print "NEKO"
        else:
            print "DRAW"
        exit()

print "DRAW"

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,u,v,m = LI()
    ud = {}
    for i in range(n):
        t = LI()
        for j in range(n):
            ud[t[j]] = (i,j)
    vd = {}
    for i in range(n):
        t = LI()
        for j in range(n):
            vd[t[j]] = (i,j)

    ma = [I() for _ in range(m)]
    ut = collections.defaultdict(bool)
    vt = collections.defaultdict(bool)
    un = 0
    vn = 0
    for t in ma:
        if t in ud:
            ut[ud[t]] = True
            ui,uj = ud[t]
            for di,dj in ddn[:4]:
                k = 1
                for i in range(1, n):
                    if not ut[(ui+di*i, uj+dj*i)]:
                        break
                    k += 1
                for i in range(-1, -n, -1):
                    if not ut[(ui+di*i, uj+dj*i)]:
                        break
                    k += 1
                if k >= n:
                    un += 1
                    if k == 1:
                        un = 1

        if t in vd:
            vt[vd[t]] = True
            vi,vj = vd[t]
            for di,dj in ddn[:4]:
                k = 1
                for i in range(1, n):
                    if not vt[(vi+di*i, vj+dj*i)]:
                        break
                    k += 1
                for i in range(-1, -n, -1):
                    if not vt[(vi+di*i, vj+dj*i)]:
                        break
                    k += 1
                if k >= n:
                    vn += 1
                    if k == 1:
                        vn = 1

        if un >= u and vn < v:
            return 'USAGI'
        if vn >= v and un < u:
            return 'NEKO'
        if un >= u and vn >= v:
            break

    return 'DRAW'



print(main())

Submission status: Accepted

Solution code:
n, u, v, m = map(int, input().split())
usa_mat = [list(map(int, input().split())) for _ in range(n)]
nek_mat = [list(map(int, input().split())) for _ in range(n)]
usa_dic = {}
nek_dic = {}
for y in range(n):
  for x in range(n):
    usa_dic[usa_mat[y][x]] = (x, y)
    nek_dic[nek_mat[y][x]] = (x, y)

usa_count = [0] * (2 * n + 2)
nek_count = [0] * (2 * n + 2)

flag = 0
usa_point = 0
nek_point = 0
for _ in range(m):
  a = int(input())
  if flag:
    continue
  
  if a in usa_dic:
    ux, uy = usa_dic[a]
    usa_count[ux] += 1
    if usa_count[ux] == n:
      usa_point += 1
    usa_count[uy + n] += 1
    if usa_count[uy + n] == n:
      usa_point += 1
    if ux + uy == n - 1:
      usa_count[-1] += 1
      if usa_count[-1] == n:
        usa_point += 1
    if ux == uy:
      usa_count[-2] += 1
      if usa_count[-2] == n:
        usa_point += 1
  
  if a in nek_dic:
    nx, ny = nek_dic[a]
    nek_count[nx] += 1
    if nek_count[nx] == n:
      nek_point += 1
    nek_count[ny + n] += 1
    if nek_count[ny + n] == n:
      nek_point += 1
    if nx + ny == n - 1:
      nek_count[-1] += 1
      if nek_count[-1] == n:
        nek_point += 1
    if nx == ny:
      nek_count[-2] += 1
      if nek_count[-2] == n:
        nek_point += 1
  
  if n == 1:
    usa_point = min(usa_point, 1)
    nek_point = min(nek_point, 1)

  if usa_point >= u and nek_point >= v:
    flag = 1
  elif usa_point >= u:
    flag = 2
  elif nek_point >= v:
    flag = 3

if flag == 2:
  print("USAGI")
elif flag == 3:
  print("NEKO")
else:
  print("DRAW")

Submission status: Accepted

Solution code:
from collections import defaultdict

n,u,v,m = map(int, raw_input().split())
U=defaultdict(tuple)
N=defaultdict(tuple)
for i in range(n):
    l=map(int, raw_input().split())
    for j in range(n):
        U[ l[j] ] = (i,j)
for i in range(n):
    l=map(int, raw_input().split())
    for j in range(n):
        N[ l[j] ] = (i,j)
Uw = [[0 for i in range(n)],[0 for i in range(n)],[0,0],0]
Nw = [[0 for i in range(n)],[0 for i in range(n)],[0,0],0]
if n==1:
    Uw[3]-=3
    Nw[3]-=3
for x in range(m):
    q=int(raw_input())
    for A in  [[U,Uw],[N,Nw]]:
        if A[0][q]!=():
            qi,qj = A[0][q]
            A[1][0][qi] += 1
            A[1][1][qj] += 1
            A[1][3] += A[1][0][qi]==n
            A[1][3] += A[1][1][qj]==n
            if qi==qj:
                A[1][2][0]+=1
                A[1][3] += A[1][2][0] ==n
            if qi==n-qj-1:
                A[1][2][1]+=1
                A[1][3] += A[1][2][1] ==n
    if Uw[3]>=u and Nw[3]<v:
        ans="USAGI"
        break
    if Nw[3]>=v and Uw[3]<u:
        ans="NEKO"
        break
    if Nw[3]>=v and Uw[3]>=u:
        ans="DRAW"
        break
else:
    ans="DRAW"
print ans
#print Uw,U
#print Nw,N

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

n, u, v, m = map(int, raw_input().split())

m1 = {}
m2 = {}

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        if n == 1:
            l = [0]
        else:
            l = [i, n + j]
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m1[lst_[j]] = l

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        if n == 1:
            l = [0]
        else:
            l = [i, n + j]
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m2[lst_[j]] = l

mu = {}
mv = {}

for loop in range(m):
    num = input()
    if num in m1:
        l = m1[num]
        for p in l:
            if not p in mu:
                mu[p] = 1
            else:
                mu[p] += 1
            if mu[p] == n:
                u -= 1
    
    if num in m2:
        l = m2[num]
        for p in l:
            if not p in mv:
                mv[p] = 1
            else:
                mv[p] += 1
            if mv[p] == n:
                v -= 1
    
    if u <= 0 or v <= 0:
        if v > 0:
            print "USAGI"
        elif u > 0:
            print "NEKO"
        else:
            print "DRAW"
        exit()

print "DRAW"

Submission status: Accepted

Solution code:
# coding: utf-8
n,u,v,m=map(int,input().split())
usa=[list(map(int,input().split())) for i in range(n)]
neko=[list(map(int,input().split())) for i in range(n)]
usadic={}
nekodic={}
usatable=[0 for i in range(2*n+2)]
nekotable=[0 for i in range(2*n+2)]
for i in range(n):
    for j in range(n):
        usadic[usa[i][j]]=[]
        nekodic[neko[i][j]]=[]
        usadic[usa[i][j]].append(i)
        nekodic[neko[i][j]].append(i)
        usadic[usa[i][j]].append(n+j)
        nekodic[neko[i][j]].append(n+j)
        if i==j:
            usadic[usa[i][j]].append(2*n)
            nekodic[neko[i][j]].append(2*n)
        if i+j==n-1:
            usadic[usa[i][j]].append(2*n+1)
            nekodic[neko[i][j]].append(2*n+1)
usacount=0
nekocount=0
for i in range(m):
    t=int(input())
    if t in usadic:
        for x in usadic[t]:
            usatable[x]+=1
            if usatable[x]==n:
                usacount+=1
    if t in nekodic:
        for x in nekodic[t]:
            nekotable[x]+=1
            if nekotable[x]==n:
                nekocount+=1
    if n==1:
        usacount=min(usacount,1)
        nekocount=min(nekocount,1)
    if usacount>=u and nekocount>=v:
        print('DRAW')
        break
    elif usacount>=u:
        print('USAGI')
        break
    elif nekocount>=v:
        print('NEKO')
        break
else:
    print('DRAW')