Party Lamps

• 버튼들이 2개단위 또는 3개 단위의 램프들을 바꾸므로, 이 버튼들의 조합으로 만들어지는 전구의 패턴은 6개 단위로 반복되는 패턴이다.
• 정확히는 '111111', '000000','010101','101010','011011','100100','110001','001110' 의 8가지 패턴이 가능하다
• 켜져있는 전구와 꺼져있는 전구의 번호들이 주어졌을때 특정 패턴에 해당하는지는, 번호를 6으로 나눈 나머지를 패턴과 비교해보면 된다.
• 각 패턴들을 만들기 위해 버튼을 눌러야하는 총 횟수를 생각해보자. '111111'은 1번버튼을 2번 눌러서 총 두번만에, 또는 1,2,3번 버튼을 한번씩 눌러서 3번만에, 아니면 이후에 같은 버튼을 2n번 더 눌러서 만들수 있다. 불가능한 경우는 버튼을 누른 총 횟수가 1번뿐일 때이다. '000000'은 어떤 횟수로든 다 만들수 있다. 이런식으로 패턴마다 따져보면, '100100','110001','001110' 은 두번 이상 버튼을 눌러야 만들수 있고, '011011'은 한번만 누르든가 아니면 세번 이상 눌러야 한다.
• 이제 끝. 버튼누른 횟수, 켜진 전구번호, 꺼진 전구번호를 갖고서 8개의 패턴들 각각에 대해서 만들수 있는 패턴인지 아닌지를 체크하면 된다.
• 전구 번호들은 O(1)개, 패턴 갯수도 O(1)개라서 계산은 O(1)에 다 끝난다. 다만 최종 출력 결과로 O(n)길이의 문자열을 만들어줘야 하기 때문에 엄밀한 시간복잡도는 O(n)..

"""Solution code for "BOJ 5508. Party Lamps".

- Problem link: https://www.acmicpc.net/problem/5508
- Solution link: http://www.teferi.net/ps/problems/boj/5508

Tags: [ad hoc]
"""

ON = '1'
OFF = '0'
PATTERNS = (
    ('111111', (1,)),
    ('000000', (0,)),
    ('010101', (0,)),
    ('101010', (0,)),
    ('011011', (0, 2)),
    ('100100', (0, 1)),
    ('110001', (0, 1)),
    ('001110', (0, 1)),
)


def main():
    N = int(input())
    C = int(input())
    on_lamps = [int(x) - 1 for x in input().split()][:-1]
    off_lamps = [int(x) - 1 for x in input().split()][:-1]

    for pat, invalid_nums in PATTERNS:
        if (
            C not in invalid_nums
            and all(pat[x % 6] == ON for x in on_lamps)
            and all(pat[x % 6] == OFF for x in off_lamps)
        ):
            print(pat * (N // 6) + pat[: N % 6])


if __name__ == '__main__':
    main()