https://codeforces.com/contest/1484/problem/C
시간 2초, 메모리 512MB
input :
- t (1 ≤ t ≤ 10000)
- n m (1 ≤ n, m ≤ 100000)
- ki, fi1, ..., fiki(1 ≤ ki, fij ≤ n)
output :
- 목표에 부합하는 정답이 없다면 "NO"를 그렇지 않은 경우에는 "YES"와 각 날짜에 같이 게임을 플레이할 친구를 출력하시오.
조건 :
-
On each of these days some friends will be available for playing, and all others will not. On each day Aleksey must choose one of his available friends to offer him playing the game (and they, of course, always agree)
해당 날짜에는 시간이 되는 친구가 있고 안 되는 친구가 존재합니다. Aleksey는 해당 날짜에 시간이 되는 친구 중에 한 명을 초대해 같이 게임을 하자 하려 합니다.(당연히 상대방은 동의합니다.) -
However, if any of them happens to be chosen strictly more than ⌈m // 2⌉(올림/ math.ceil) times, then all other friends are offended
만약 친구들 중 (m + 1) // 2번 보다 더 많이 게임에 참여한 친구가 있다면 다른 이들이 상처를 받습니다. 그리고 상처를 받게 하고 싶지 않아 합니다.
일단 문제이해가 제일 어려웠다.
입력받는 것은 n, m 친구의 수와 날짜이고.
그 아래로 m개의 줄에는 맨 처음 원소는 이후에 몇 명의 친구들이 가능한지를 뜻하고. 그 뒤로는 각 친구들의 숫자가 들어온다.
생각보다 쉬운것은. 1명의 친구만 가능한 경우에는 그 친구를 선택해야 한다는 것이다.
이렇게 했을 떄 이미 제한 횟수보다 크다면 "NO"를 출력하면 된다.
AC를 받은 코드에 반례가 존재하는 것 같아 코드를 추가했다.
사실 1명인 것을 제외한 날짜에는 추가적인 선택지가 존재한다. 그렇다면 가능한 친구들 중 한 명을 선택하면 되는 것이다.
그런데 그 모두가 불가능한 날짜가 있으면 NO를 출력해줘야 한다. 하지만 테케에는 이 예제가 없는 것 같다.
import sys
from math import ceil
for _ in range(int(sys.stdin.readline())):
n, m = map(int, sys.stdin.readline().split())
date = []
friends = [0] * (n + 1)
ans = [0] * m
limit = ceil(m / 2)
for i in range(m):
temp = list(map(int, sys.stdin.readline().split()))
date.append(temp[1:])
if temp[0] == 1:
friends[temp[1]] += 1
ans[i] = temp[1]
continue
if max(friends) > limit:
print("NO")
continue
for i in range(m):
if ans[i] != 0:
continue
for j in range(len(date[i])):
if friends[date[i][j]] < limit:
friends[date[i][j]] += 1
ans[i] = date[i][j]
break
if min(ans) == 0:
print("NO")
continue
print("YES")
print(*ans)
