結果
問題 | No.1576 織姫と彦星 |
ユーザー | McGregorsh |
提出日時 | 2022-07-21 19:27:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,105 ms / 2,000 ms |
コード長 | 3,173 bytes |
コンパイル時間 | 662 ms |
コンパイル使用メモリ | 87,028 KB |
実行使用メモリ | 95,100 KB |
最終ジャッジ日時 | 2023-09-16 01:33:26 |
合計ジャッジ時間 | 35,864 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 218 ms
92,816 KB |
testcase_01 | AC | 215 ms
92,856 KB |
testcase_02 | AC | 219 ms
92,932 KB |
testcase_03 | AC | 218 ms
93,196 KB |
testcase_04 | AC | 217 ms
92,884 KB |
testcase_05 | AC | 220 ms
94,192 KB |
testcase_06 | AC | 225 ms
94,080 KB |
testcase_07 | AC | 401 ms
94,600 KB |
testcase_08 | AC | 354 ms
94,472 KB |
testcase_09 | AC | 232 ms
94,272 KB |
testcase_10 | AC | 734 ms
94,816 KB |
testcase_11 | AC | 237 ms
94,448 KB |
testcase_12 | AC | 563 ms
94,916 KB |
testcase_13 | AC | 874 ms
94,908 KB |
testcase_14 | AC | 648 ms
94,984 KB |
testcase_15 | AC | 650 ms
94,868 KB |
testcase_16 | AC | 780 ms
95,020 KB |
testcase_17 | AC | 697 ms
94,900 KB |
testcase_18 | AC | 341 ms
94,740 KB |
testcase_19 | AC | 405 ms
94,952 KB |
testcase_20 | AC | 694 ms
94,476 KB |
testcase_21 | AC | 739 ms
94,744 KB |
testcase_22 | AC | 769 ms
94,824 KB |
testcase_23 | AC | 284 ms
94,656 KB |
testcase_24 | AC | 284 ms
94,700 KB |
testcase_25 | AC | 875 ms
95,008 KB |
testcase_26 | AC | 387 ms
94,856 KB |
testcase_27 | AC | 241 ms
94,444 KB |
testcase_28 | AC | 705 ms
94,968 KB |
testcase_29 | AC | 385 ms
94,916 KB |
testcase_30 | AC | 225 ms
94,104 KB |
testcase_31 | AC | 402 ms
94,608 KB |
testcase_32 | AC | 600 ms
94,652 KB |
testcase_33 | AC | 1,070 ms
95,100 KB |
testcase_34 | AC | 241 ms
94,528 KB |
testcase_35 | AC | 464 ms
94,836 KB |
testcase_36 | AC | 273 ms
94,708 KB |
testcase_37 | AC | 1,043 ms
94,920 KB |
testcase_38 | AC | 727 ms
94,924 KB |
testcase_39 | AC | 501 ms
95,040 KB |
testcase_40 | AC | 443 ms
94,764 KB |
testcase_41 | AC | 481 ms
94,628 KB |
testcase_42 | AC | 247 ms
94,276 KB |
testcase_43 | AC | 312 ms
94,680 KB |
testcase_44 | AC | 940 ms
95,068 KB |
testcase_45 | AC | 427 ms
94,844 KB |
testcase_46 | AC | 686 ms
94,932 KB |
testcase_47 | AC | 325 ms
94,808 KB |
testcase_48 | AC | 547 ms
94,668 KB |
testcase_49 | AC | 481 ms
94,836 KB |
testcase_50 | AC | 242 ms
94,384 KB |
testcase_51 | AC | 286 ms
94,684 KB |
testcase_52 | AC | 935 ms
94,848 KB |
testcase_53 | AC | 629 ms
94,856 KB |
testcase_54 | AC | 766 ms
94,864 KB |
testcase_55 | AC | 1,105 ms
94,892 KB |
testcase_56 | AC | 991 ms
94,880 KB |
testcase_57 | AC | 230 ms
94,336 KB |
testcase_58 | AC | 378 ms
94,880 KB |
ソースコード
import sys, re from fractions import Fraction from math import ceil, floor, sqrt, pi, factorial, gcd from copy import deepcopy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import accumulate, product, combinations, combinations_with_replacement, permutations from bisect import bisect, bisect_left, bisect_right from functools import reduce from decimal import Decimal, getcontext def i_input(): return int(input()) def i_map(): return map(int, input().split()) def i_list(): return list(i_map()) def i_row(N): return [i_input() for _ in range(N)] def i_row_list(N): return [i_list() for _ in range(N)] def s_input(): return input() def s_map(): return input().split() def s_list(): return list(s_map()) def s_row(N): return [s_input for _ in range(N)] def s_row_str(N): return [s_list() for _ in range(N)] def s_row_list(N): return [list(s_input()) for _ in range(N)] def lcm(a, b): return a * b // gcd(a, b) def get_distance(x1, y1, x2, y2): d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) return d def rotate(table): n_fild = [] for x in zip(*table[::-1]): n_fild.append(x) return n_fild sys.setrecursionlimit(10 ** 7) INF = float('inf') MOD = 10 ** 9 + 7 MOD2 = 998244353 ###関数コピーしたか?### def main(): n = int(input()) start, end = i_map() stone = i_list() nums = [set() for i in range(n+2)] for i in range(n): bit_i = format(stone[i], 'b') bit_i_zero = bit_i.zfill(50) for j in range(n): if i == j: continue bit_j = format(stone[j], 'b') bit_j_zero = bit_j.zfill(50) cou = 0 for k in range(50): if bit_i_zero[k] != bit_j_zero[k]: cou += 1 if cou == 2: break if cou == 1: nums[i+1].add(j+1) nums[j+1].add(i+1) start_bit = format(start, 'b') end_bit = format(end, 'b') start_bit_zero = start_bit.zfill(50) end_bit_zero = end_bit.zfill(50) nn = 0 for i in range(50): if start_bit_zero[i] != end_bit_zero[i]: nn += 1 if nn == 1: print(0) exit() for i in range(n): point_i = format(stone[i], 'b') point_i_zero = point_i.zfill(50) cou1 = 0 cou2 = 0 for j in range(50): if point_i_zero[j] != start_bit_zero[j]: cou1 += 1 if point_i_zero[j] != end_bit_zero[j]: cou2 += 1 if cou1 == 1: nums[0].add(i+1) nums[i+1].add(0) if cou2 == 1: nums[n+1].add(i+1) nums[i+1].add(n+1) greets = [] for i in range(n+2): lines = list(nums[i]) greets.append(lines) que = deque() que.append(0) dist = [INF] * (n+2) dist[0] = 0 while que: point = que.popleft() for i in greets[point]: if dist[i] == INF: dist[i] = dist[point] + 1 que.append(i) #print(greets) #print(dist) if dist[-1] == INF: print(-1) else: print(dist[-1]-1) if __name__ == '__main__': main()