結果

問題 No.2148 ひとりUNO
ユーザー 👑 rin204rin204
提出日時 2022-12-05 05:02:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 187 ms / 2,000 ms
コード長 8,270 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,484 KB
実行使用メモリ 78,148 KB
最終ジャッジ日時 2024-04-20 08:33:34
合計ジャッジ時間 8,056 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
53,888 KB
testcase_01 AC 177 ms
78,016 KB
testcase_02 AC 153 ms
77,484 KB
testcase_03 AC 156 ms
77,056 KB
testcase_04 AC 158 ms
77,020 KB
testcase_05 AC 161 ms
77,568 KB
testcase_06 AC 164 ms
77,184 KB
testcase_07 AC 148 ms
77,696 KB
testcase_08 AC 156 ms
77,056 KB
testcase_09 AC 174 ms
77,304 KB
testcase_10 AC 152 ms
77,148 KB
testcase_11 AC 163 ms
77,440 KB
testcase_12 AC 177 ms
77,772 KB
testcase_13 AC 155 ms
77,508 KB
testcase_14 AC 154 ms
78,148 KB
testcase_15 AC 158 ms
77,312 KB
testcase_16 AC 180 ms
77,116 KB
testcase_17 AC 175 ms
77,000 KB
testcase_18 AC 176 ms
77,056 KB
testcase_19 AC 180 ms
76,928 KB
testcase_20 AC 180 ms
77,056 KB
testcase_21 AC 183 ms
76,964 KB
testcase_22 AC 187 ms
77,056 KB
testcase_23 AC 182 ms
77,160 KB
testcase_24 AC 177 ms
77,440 KB
testcase_25 AC 181 ms
77,312 KB
testcase_26 AC 169 ms
77,184 KB
testcase_27 AC 168 ms
76,928 KB
testcase_28 AC 180 ms
77,928 KB
testcase_29 AC 181 ms
77,440 KB
testcase_30 AC 162 ms
76,928 KB
testcase_31 AC 164 ms
77,036 KB
testcase_32 AC 171 ms
77,144 KB
testcase_33 AC 159 ms
77,268 KB
testcase_34 AC 166 ms
76,952 KB
testcase_35 AC 165 ms
77,440 KB
testcase_36 AC 163 ms
76,928 KB
testcase_37 AC 168 ms
77,056 KB
testcase_38 AC 166 ms
77,240 KB
testcase_39 AC 42 ms
53,888 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def popcount(n: int) -> int:
    n -= ((n >> 1) & 0x5555555555555555)
    n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
    n = (n + (n >> 4)) & 0x0f0f0f0f0f0f0f0f
    n += ((n >> 8) & 0x00ff00ff00ff00ff)
    n += ((n >> 16) & 0x0000ffff0000ffff)
    n += ((n >> 32) & 0x00000000ffffffff)
    return n & 0x7f
    
class Bitset:
    def __init__(self, n: int) -> None:
        self.n = n
        self.m = (n + 62) // 63
        self.A = [0] * self.m

    def __len__(self) -> int:
        return self.n
    
    @property
    def size(self) -> int:
        return self.n

    def __str__(self) -> str:
        S = []
        for a in self.A:
            S.append(bin(a)[2:].zfill(63)[::-1])
        S = "".join(S)
        return S[:self.n][::-1]

    def __getitem__(self, ind: int) -> int:
        i = ind // 63
        j = ind - i * 63
        return self.A[i] >> j & 1

    def __setitem__(self, ind: int, k: int) -> None:
        i = ind // 63
        j = ind - i * 63
        if (self.A[i] >> j & 1) != k:
            self.A[i] ^= 1 << j
        else:
            pass

    def rev(self, ind: int) -> None:
        i = ind // 63
        j = ind - i * 63
        self.A[i] ^= 1 << j

    def count(self) -> int:
        ret = 0
        for a in self.A:
            ret += popcount(a)
        return ret

    def __sum__(self) -> int:
        return self.count()

    def resize(self, n: int) -> None:
        m = (n + 62) // 63
        if m > self.m:
            self.A += [0] * (m - self.m)
        else:
            self.A = self.A[:m]
            j = n % 63
            if j != 0:
                self.A[-1] &= (1 << j) - 1
            else:
                pass
        self.n = n
        self.m = m
        
    def __and__(self, other: 'Bitset') -> 'Bitset':
        if self.n < other.n:
            n = self.n
        else:
            n = other.n

        ret = Bitset(n)
        for i, (a, b) in enumerate(zip(self.A, other.A)):
            ret.A[i] = a & b
        
        return ret

    def __iand__(self, other: 'Bitset') -> 'Bitset':
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for i in range(m):
            self.A[i] &= other.A[i]
        for i in range(m, self.m):
            self.A[i] = 0
        return self

    def __or__(self, other: 'Bitset') -> 'Bitset':
        if self.n > other.n:
            n = self.n
        else:
            n = other.n
        
        ret = Bitset(n)
        for i in range(ret.m):
            if i < self.m and i < other.m:
                ret.A[i] = self.A[i] | other.A[i]
            elif i < self.m:
                ret.A[i] = self.A[i]
            else:
                ret.A[i] = other.A[i]
            
        return ret

    def __ior__(self, other: 'Bitset') -> 'Bitset':
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for i in range(m):
            self.A[i] |= other.A[i]
        if self.n < other.n:            
            x = self.n % 63
            if x != 0:
                mask = (1 << x) - 1
                self.A[-1] &= mask
        else:
            pass
        return self

    def __xor__(self, other: 'Bitset') -> 'Bitset':
        if self.n > other.n:
            n = self.n
        else:
            n = other.n
        
        ret = Bitset(n)
        for i in range(ret.m):
            if i < self.m and i < other.m:
                ret.A[i] = self.A[i] ^ other.A[i]
            elif i < self.m:
                ret.A[i] = self.A[i]
            else:
                ret.A[i] = other.A[i]
            
        return ret

    def __ixor__(self, other: 'Bitset') -> 'Bitset':
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for i in range(m):
            self.A[i] ^= other.A[i]
        if self.n < other.n:
            x = self.n % 63
            if x != 0:
                mask = (1 << x) - 1
                self.A[-1] &= mask
        else:
            pass
        return self

    def and_count(self, other: 'Bitset') -> int:
        ret = 0
        for a, b in zip(self.A, other.A):
            ret += popcount(a & b)
        return ret

    def or_count(self, other: 'Bitset') -> int:
        ret = 0
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for a, b in zip(self.A[:m], other.A[:m]):
            ret += popcount(a | b)
        
        for a in self.A[m:]:
            ret += popcount(a)
        
        for a in other.A[m:]:
            ret += popcount(a)

        return ret

    def xor_count(self, other: 'Bitset') -> int:
        ret = 0
        if self.m < other.m:
            m = self.m
        else:
            m = other.m
        for a, b in zip(self.A[:m], other.A[:m]):
            ret += popcount(a ^ b)
        
        for a in self.A[m:]:
            ret += popcount(a)
        
        for a in other.A[m:]:
            ret += popcount(a)

        return ret

    def __rshift__(self, k: int) -> 'Bitset':
        ret = Bitset(self.n)
        x = k // 63
        for i in range(x, self.m):
            ret.A[i - x] = self.A[i]
        k -= x * 63
        if k != 0:
            mask = (1 << k) - 1
            rk = 63 - k
            for i, a in enumerate(ret.A):
                if i != 0:
                    ret.A[i - 1] |= (a & mask) << (rk)
                ret.A[i] = a >> k
        else:
            pass
        return ret

    def __irshift__(self, k: int) -> 'Bitset':
        x = k // 63
        for i in range(x, self.m):
            self.A[i - x] = self.A[i]
        for i in range(self.m - x, self.m):
            self.A[i] = 0
        k -= x * 63
        if k != 0:
            mask = (1 << k) - 1
            rk = 63 - k
            for i, a in enumerate(self.A):
                if i != 0:
                    self.A[i - 1] |= (a & mask) << (rk)
                self.A[i] = a >> k
        else:
            pass
        return self

    def __lshift__(self, k: int) -> 'Bitset':
        ret = Bitset(self.n)
        x = k // 63
        for i in range(x, self.m):
            ret.A[i] = self.A[i - x]
        k -= x * 63
        if k != 0:
            rk = 63 - k
            mask = (1 << rk) - 1
            for i in range(self.m - 1, -1, -1):
                ret.A[i] &= mask
                ret.A[i] <<= k
                if i != 0:
                    ret.A[i] |= ret.A[i - 1] >> rk
        else:
            pass
        return ret

    def __ilshift__(self, k: int) -> 'Bitset':
        x = k // 63
        for i in range(self.m - 1, x - 1, -1):
            self.A[i] = self.A[i - x]
        for i in range(x - 1, -1, -1):
            self.A[i] = 0
        k -= x * 63
        if k != 0:
            rk = 63 - k
            mask = (1 << rk) - 1
            for i in range(self.m - 1, -1, -1):
                self.A[i] &= mask
                self.A[i] <<= k
                if i != 0:
                    self.A[i] |= self.A[i - 1] >> rk
        else:
            pass
        return self

def solve(n, C):
    R = Bitset(n)
    G = Bitset(n)
    B = Bitset(n)
    cr = 0
    cg = 0
    cb = 0
    for c, d in C:
        d = int(d) - 1
        if c == "R":
            R[d] = 1
            cr += 1
        elif c == "G":
            G[d] = 1
            cg += 1
        else:
            B[d] = 1
            cb += 1
    if [cr, cg, cb].count(0) == 2:
        return True
    elif cr == 0:
        return G.and_count(B) > 0
    elif cg == 0:
        return R.and_count(B) > 0
    elif cb == 0:
        return R.and_count(G) > 0
    
    RGB = R & G & B
    crgb = RGB.count()
    if 1 in [cr, cg, cb] and crgb:
        return True
    if crgb >= 2:
        return True
    crg = R.and_count(G)
    crb = R.and_count(B)
    cgb = G.and_count(B)
    C = [crg, crb, cgb]
    for i in range(3):
        for j in range(3):
            if i == j:
                continue
            if C[i] >= 1 and C[j] >= 2:
                return True
            if C[i] == 1 and C[j] == 1 and crgb == 0:
                return True
    return False


    

for _ in range(int(input())):
    n = int(input())
    C = [input().split() for _ in range(n)]
    if solve(n, C):
        print("YES")
    else:
        print("NO")
0