Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

蟻

  大きなチェス盤上に、それぞれ１から N までの番号が割り振られた N 匹の蟻がいます。図のように、チェス盤は H×W のマスからなる長方形で、北西角を白として、白マスと黒マスが交互に並んでいます。

  

  最初、どの蟻もチェス盤のマスの中にいて、東または南を向いています。１つのマスの中に２匹以上の蟻がいることはありません。

  今、蟻たちが一斉に動き出します。すべての蟻は 1 単位時間に向いている方向のマスに１つ移動します。ただし、移動先がチェス盤の外の場合、落下してチェス盤から姿を消します。

  チェス盤上で２匹の蟻が同じマスに入ると、それらの蟻は以下のような行動をとります：

 そのマスの色が白ならば、東方向に進んでいた蟻は南方向へ、南方向に進んでいた蟻は東方向へ向きを変える。

 そのマスの色が黒ならば、それぞれの蟻は進む方向を維持する。

  チェス盤の大きさと蟻の情報が与えられたとき、落下する順番に蟻の番号を報告するプログラムを作成せよ。ただし、同じ時刻に複数の蟻が落下する場合は、番号がより小さい方を先に報告する。
  

  

Input

  入力は以下の形式で与えられる。

W H N
x1 y1 d1
x2 y2 d2
:
xN yN dN

１行目にチェス盤の東西方向のマスの数 W と南北方向のマスの数 H (2 ≤ W, H ≤ 109) と蟻の数 N (1 ≤ N ≤ 200000) が与えられる。続く N 行に i 番目の蟻の東西方向の位置 xi (1 ≤ xi ≤ W)、南北方向の位置 yi (1 ≤ yi ≤ H)、向きを表す文字 di（東向きの場合「E」、南向きの場合「S」）が与えられる。ここで、チェス盤の北西角のマスを (1,1)、x が増加する方向を東、y が増加する方向を南とする。

Output

落下する順番に、蟻の番号を１行ずつ出力する。

Sample Input 1

3 3 3
2 1 S
1 2 E
2 2 E

Sample Output 1

3
1
2

Sample Input 2

5 4 3
3 1 S
2 2 E
1 3 E

Sample Output 2

2
3
1



Sample input:
3 3 3
2 1 S
1 2 E
2 2 E


Sample output:
3
1
2

Submission status: Wrong Answer

Solution code:
class Ant:
    def __init__(self, params):
        self.live = True
        self.x = int(params[0])
        self.y = int(params[1])
        self.d = 0 if params[2] == "E" else 1

W, H, N = list(map(int, input().split()))
ants = []

for i in range(N):
    a = Ant(input().split())
    ants.append(a)

death = 0
while death < N:
    board = [[ (i+j)%2-2 for j in range(H)] for i in range(W)]
    for i, a in enumerate(ants):
        if not a.live:
            continue
        
        if a.d == 0:
            a.x += 1
        else:
            a.y += 1

        if a.x >= W or a.y >= H:
            a.live = False
            print(i+1)
            death += 1
        else:
            b = board[a.x][a.y]
            if  b == -2:
                board[a.x][a.y] = i
            elif b >= 0:
                a.d = 1 - a.d
                ants[b].d = 1 - ants[b].d

Submission status: Time Limit Exceeded

Solution code:
class Ant:
    def __init__(self, params):
        self.live = True
        self.x = int(params[0])-1
        self.y = int(params[1])-1
        self.d = 0 if params[2] == "E" else 1

W, H, N = list(map(int, input().split()))
ants = []

for i in range(N):
    a = Ant(input().split())
    ants.append(a)

death = 0
while death < N:
    for i, a in enumerate(ants):
        if not a.live:
            continue
        
        if a.d == 0:
            a.x += 1
        else:
            a.y += 1

        if a.x >= W or a.y >= H:
            a.live = False
            print(i+1)
            death += 1
        else:
            if (a.x+a.y)%2 == 0:
                try:
                    b = list(filter(lambda x: x.x == a.x and x.y == a.y, ants))[0]
                except:
                    pass
                else:
                    b.d = 1-b.d
                    a.d = 1-a.d

Submission status: Memory Limit Exceeded

Solution code:
class Ant:
    def __init__(self, params):
        self.live = True
        self.x = int(params[0])
        self.y = int(params[1])
        self.d = 0 if params[2] == "E" else 1

W, H, N = list(map(int, input().split()))
ants = []

for i in range(N):
    a = Ant(input().split())
    ants.append(a)

death = 0
while death < N:
    board = [[ (i+j)%2-2 for j in range(H+1)] for i in range(W+1)]
    for i, a in enumerate(ants):
        if not a.live:
            continue
        
        if a.d == 0:
            a.x += 1
        else:
            a.y += 1

        if a.x > W or a.y > H:
            a.live = False
            print(i+1)
            death += 1
        else:
            b = board[a.x][a.y]
            if  b == -2:
                board[a.x][a.y] = i
            elif b >= 0:
                a.d = 1 - a.d
                ants[b].d = 1 - ants[b].d

Submission status: Memory Limit Exceeded

Solution code:
class Ant:
    def __init__(self, params):
        self.live = True
        self.x = int(params[0])-1
        self.y = int(params[1])-1
        self.d = 0 if params[2] == "E" else 1

W, H, N = list(map(int, input().split()))
ants = []

for i in range(N):
    a = Ant(input().split())
    ants.append(a)

death = 0
while death < N:
    board = [[ (i+j)%2-2 for j in range(H)] for i in range(W)]
    for i, a in enumerate(ants):
        if not a.live:
            continue
        
        if a.d == 0:
            a.x += 1
        else:
            a.y += 1

        if a.x >= W or a.y >= H:
            a.live = False
            print(i+1)
            death += 1
        else:
            b = board[a.x][a.y]
            if  b == -2:
                board[a.x][a.y] = i
            elif b >= 0:
                a.d = 1 - a.d
                ants[b].d = 1 - ants[b].d