提出 #25776081


ソースコード 拡げる

import math
import copy
import sys
import functools
from decimal import *
import collections
from collections import defaultdict
import itertools
from heapq import heappush, heappop, heapify
import random
sys.setrecursionlimit(10**8)
#A = []
#S = input()
#S = input()
N = int(input())
#A = list(map(int, input().split()))
#A = list(map(int, input().split()))
#N, K = map(int, input().split())
#A, B = map(int, input().split())
#A = list(map(int, input().split()))
#B = list(map(int, input().split()))
#C = [1]*N
#mod = 1000000007
mod = 998244353
#mod = M*M
def add(a, b):
    return (a + b) % mod

def sub(a, b):
    return (a + mod - b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

def cumsum(xs):
    result = [xs[0]]
    for x in xs[1:]:
        result.append(result[-1] + x)
    return result

def cumsub(xs): 
    result = [xs[0]]
    for x in range(1, len(xs[1:])+1):
        result.append(xs[x] - xs[x-1])
    return result

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = collections.Counter()
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n /= prime_factor_table[n]
        n = int(n)
    prime_count[n] += 1
    
    return prime_count

def isPrime(n) : 
  
    if (n < 2) : 
        return False
    for i in range(2, n + 1) : 
        if (i * i <= n and n % i == 0) : 
            return False
    return True

def smallest_prime_factors():
    n = 1000000
    spf = [0] * (n+1)
    for i in range(0, n+1):
        spf[i] = i
    d = int(n ** (1/2))
    for i in range(2,d+1):
        if spf[i] == i:
            for j in range(i*i, n+1, i):
                if spf[j] == j:
                    spf[j] = i
    return spf

def fac_spf(x, spf):
    ret = {}
    while x != 1:
        if spf[x] not in ret:
            ret[spf[x]] = 1
        else:
            ret[spf[x]] +=1
        print(x)
        x = int(x/spf[x])
    return ret

def gcd(x, y):# 最大公約数
    if y == 0:
        return x
    else:
        return gcd(y,x%y) 

def lcm(a, b):
    return a * b / gcd(a, b)

def extGCD(a,b): # ax+by=gcd(a,b)
    x, y, u, v = 1, 0, 0, 1
    while b:
        k = a // b
        x -= k * u
        y -= k * v
        x, u = u, x
        y, v = v, y
        a, b = b, a % b
    return x, y

def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x % 1000000007
    x = x*x % 1000000007
    n = n >> 1
  return ans

class Node:
    def __init__(self, data):
        self.data = data
        self.fo = []
        self.count = 0



class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

def ind_sort(list_l):
    indices = [*range(len(list_l))]
    sorted_indices = sorted(indices, key=lambda i: list_l[i])
    sorted_num = [list_l[i] for i in sorted_indices]
    return (sorted_num, sorted_indices)
S = []
T = []
for i in range(N):
    S.append(input())
for i in range(N):
    T.append(input())

Sa = [[],[],[],[]]
Ta = [[],[],[],[]]

sma = [0,0]
smi = [N-1,N-1]

for i in range(len(S)):
    for j in range(len(S[i])):
        if S[i][j] == "#":
            if sma[0] < j:
                sma[0] = j
            if smi[0] > j:
                smi[0] = j
    if "#" in S[i]:
        if sma[1] < i:
            sma[1] = i
        if smi[1] > i:
            smi[1] = i

center = ((sma[0] + smi[0])/2, ((sma[1] + smi[1])/2)*(-1))
for i in range(len(S)):
    for j in range(len(S[i])):
        if S[i][j] == "#":
            ii = i*(-1)
            Sa[0].append((j-center[0],ii-center[1]))
            Sa[1].append(((ii-center[1])*(-1),j-center[0]))
            Sa[2].append(((ii-center[1]),(j-center[0])*(-1)))
            Sa[3].append(((j-center[0])*(-1),(ii-center[1])*(-1)))

sma = [0,0]
smi = [N-1,N-1]

for i in range(len(T)):
    for j in range(len(T[i])):
        if T[i][j] == "#":
            if sma[0] < j:
                sma[0] = j
            if smi[0] > j:
                smi[0] = j
    if "#" in T[i]:
        if sma[1] < i:
            sma[1] = i
        if smi[1] > i:
            smi[1] = i

center = ((sma[0] + smi[0])/2, ((sma[1] + smi[1])/2)*(-1))
for i in range(len(T)):
    for j in range(len(T[i])):
        if T[i][j] == "#":
            ii = i*(-1)
            Ta[0].append((j-center[0],ii-center[1]))
            Ta[1].append(((ii-center[1])*(-1),j-center[0]))
            Ta[2].append(((ii-center[1]),(j-center[0])*(-1)))
            Ta[3].append(((j-center[0])*(-1),(ii-center[1])*(-1)))

for i in range(4):
    Sa[i] = set(Sa[i])
    Ta[i] = set(Ta[i])
ans = 0
for i in Sa:
    for j in Ta:
        if i == j:
            ans = 1
if ans == 1:
    print("Yes")
else:
    print("No")

提出情報

提出日時
問題 C - Shapes
ユーザ lefter
言語 Python (3.8.2)
得点 300
コード長 6733 Byte
結果 AC
実行時間 530 ms
メモリ 68796 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 300 / 300
結果
AC × 4
AC × 20
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
ケース名 結果 実行時間 メモリ
hand_01.txt AC 35 ms 10472 KiB
hand_02.txt AC 31 ms 10472 KiB
hand_03.txt AC 29 ms 10364 KiB
hand_04.txt AC 33 ms 10368 KiB
hand_05.txt AC 32 ms 10356 KiB
hand_06.txt AC 50 ms 10404 KiB
hand_07.txt AC 50 ms 10400 KiB
random_01.txt AC 68 ms 20740 KiB
random_02.txt AC 26 ms 10532 KiB
random_03.txt AC 80 ms 22096 KiB
random_04.txt AC 57 ms 14552 KiB
random_05.txt AC 72 ms 15868 KiB
random_06.txt AC 71 ms 15864 KiB
random_07.txt AC 322 ms 68220 KiB
random_08.txt AC 371 ms 68308 KiB
random_09.txt AC 530 ms 68796 KiB
sample_01.txt AC 33 ms 10532 KiB
sample_02.txt AC 31 ms 10552 KiB
sample_03.txt AC 33 ms 10560 KiB
sample_04.txt AC 35 ms 10536 KiB