문제

https://www.acmicpc.net/problem/1803

입력
4 5
3 5 2 5
4 4 4 1 3
출력
0110
10110

point

판별함수

• 활 판별 함수(내가 '활'이려면)
  • 내가 바라보고 있는 상대방이 '방패'여야 한다.
  • 나를 바라보는 모든 상대가 '방패'여야 한다.
• 활 판별 : 불가능 (내가 '활'이 안 되는 이유와 후속 처리)
  • 나를 바라보는 상대 중 '방패'가 안 되는 학생A가 있다.
    : 학생A(상대 팀)를 바라보는 우리 팀 학생 중 '활'이 한 명도 없다.
  • 내가 '방패'로 설정되어도 나를 보는 상대방에 대한 포지션은 영향이 없다.
    (즉, 나를 보는 상대의 포지션 결정에 '나'의 포지션은 영향을 미치지 않았다.)
  • 함수 내에서 지정해둔 상대방들에 대한 포지션 그대로 이어가도 된다.
  • 1) 내 포지션 '방패'로 설정, 2)내가 바라보는 상대방의 포지션 다시 판별
• 방패 판별 함수(내가 '방패'이려면)
  • 나를 바라보는 모든 상대 중 '활'이 적어도 한 명 있어야 한다.
• 방패 판별 : 불가능 (내가 '방패'가 안 되는 이유와 후속 처리)
  • 나를 바라보는 모든 상대가 '방패'다.
    : 나를 바라보는 모든 상대가 다른 '활'에게 맞고 있다.
  • 내가 '활'로 재설정 되어도 상대방의 포지션들은 여전히 '방패'로 유지되어야 한다.
  • 나만 '활'로 바꿔주면 된다.

활 or 방패

• 포지션 선택은 둘 중 하나다.
• 그러므로 활이 안 된다면 방패고, 방패가 안 된다면 활이다.
• 예를들어, 활이 안된다고 판별된 학생의 포지션을 방패로 설정 할 때 방패가 되는지 판별하는 함수를 돌려줄 필요 없이 바로 포지션을 설정하면 된다.

if flag == -1:
  my_state[num] = 1 #bow(my,num)
  return -1

매번 모든 상대를 순회X

• 매번 자신을 보고 있는 상태를 찾기위해 모든 상대방을 순회했더니 시간초과 발생
• 처음 모든 학생들에 대해 자신을 보고 있는 상대방 정보를 저장해놓는다.

a_lookme = [[] for _ in range(an+1)]
b_lookme = [[] for _ in range(bn+1)]
for i in range(1,an+1):
  b_lookme[a[i]].append(i)
for i in range(1,bn+1):
  a_lookme[b[i]].append(i)

python에서 재귀를 사용할 때 재귀 깊이 제한을 풀어 주는 것은 필수

import sys
sys.setrecursionlimit(10**6)

전체 코드

import sys
sys.setrecursionlimit(10**6)

an, bn = [int(x) for x in input().split()]

a = [0] + [int(x) for x in input().split()]
b = [0] + [int(x) for x in input().split()]
state_a = [-1]*(an+1)
state_b = [-1]*(bn+1)

a_lookme = [[] for _ in range(an+1)]
b_lookme = [[] for _ in range(bn+1)]
for i in range(1,an+1):
  b_lookme[a[i]].append(i)
for i in range(1,bn+1):
  a_lookme[b[i]].append(i)

def shield(team, num):
  global a, b, state_a, state_b, a_lookme, b_lookme
  if team == a:
    my = a
    my_state = state_a
    your = b
    your_state = state_b
    lookme = a_lookme
  else:
    my = b
    my_state = state_b
    your = a
    your_state = state_a
    lookme = b_lookme
  
  my_state[num] = 0
  flag = -1
  for i in lookme[num]:
      if your_state[i] == 1:
        flag = 1
        continue
      if your_state[i] == 0:
        continue
      if bow(your, i) != -1:
        flag = 1
  if flag == -1:
    my_state[num] = 1 #bow(my,num)
    return -1
  else:
    return 1


def bow(team, num):
  global a, b, state_a, state_b, a_lookme, b_lookme
  if team == a:
    my = a
    my_state = state_a
    your = b
    your_state = state_b
    lookme = a_lookme
  else:
    my = b
    my_state = state_b
    your = a
    your_state = state_a
    lookme = b_lookme

  if your_state[my[num]] == 1:
    my_state[num] = 0
    return -1
  my_state[num] = 1      
  your_state[my[num]] = 0
  for i in lookme[num]:
      if your_state[i] == 0:
        continue
      if your_state[i] == 1:
        my_state[num] = 0 #shield(my,num)
        shield(your,my[num])
        return -1
      if shield(your,i) == -1:
        # print(f"{i}에서 방패 불가능")
        my_state[num] = 0 #shield(my,num)
        shield(your,my[num])
        return -1
  return 1

for i in range(1, an+1):
  if state_a[i] == -1:
    bow(a,i)
for i in range(1, bn+1):
  if state_b[i] == -1:
    bow(b,i)

print(*state_a[1:])
print(*state_b[1:])