結果

問題 No.2224 UFO Game
ユーザー kusirakusira
提出日時 2023-02-24 21:31:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 155 ms / 2,000 ms
コード長 16,496 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 91,672 KB
最終ジャッジ日時 2024-09-13 05:07:00
合計ジャッジ時間 3,243 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#Python3/Pypy3
#-------------------------------------------------------------------
from bisect import *
import heapq
import collections
from collections import deque
from queue import Queue
from itertools import groupby
import itertools
import math
import array
import string
import copy
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
#------------------------------------------------------------------
INF = 10**18
MOD = 10**9+7
mod = 998244353
def YesNo(b): print("Yes") if b else print("No")
def YESNO(b): print("YES") if b else print("NO")
#---------------------------------------------------------------------
import sys
sys.setrecursionlimit(10 ** 5 + 10000)
input = sys.stdin.readline ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LIS(): return list(map(int, SI()))
def LA(f): return list(map(f, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return input().strip('\n')
def MS(): return input().split()
def LS(): return list(input().strip('\n'))
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def LMS(rows_number): return [MS() for _ in range(rows_number)]
#------------------------------------------------------------------------
######
def transpose(A): #
A_t = []
for i in range(len(A[0])) :
tmp = []
for v in A :
tmp.append(v[i])
A_t.append(tmp)
return A_t
def removeDuplicates_2D(A): #
return list(map(list, set(map(tuple, A))))
def cumulativeSum_1D(A): #A
return list(itertools.accumulate(A))
def cumulativeSum_2D(S): #S =>
h = len(S)
w = len(S[0])
CS = [[0 for _ in range(w)]for _ in range(h)]
CCS = [[0 for _ in range(w)]for _ in range(h)]
for i in range(h):
for j in range(w):
if(j==0):
CS[i][0] = S[i][0]
else:
CS[i][j] = CS[i][j-1] + S[i][j]
for i in range(h):
for j in range(w):
if(i==0):
CCS[0][j] = CS[0][j]
else:
CCS[i][j] = CCS[i-1][j] + CS[i][j]
return CCS
def string_to_runLength(S: str): #/
grouped = groupby(S)
res = []
for k, v in grouped:
res.append((k, int(len(list(v)))))
return res
def runLength_to_string(L: "list[tuple]"): # =>
res = ""
for c, n in L:
res += c * int(n)
return res
def bfs(i,m = mod): # i: m:mod(998244353) => dist,pre,dp
dist = [-1] * n
dp = [0] * n
pre = [-1] * n
que = deque()
dp[i] = 1
dist[i] = 0
que.append(i)
while que:
v = que.popleft()
for next_v in G[v]:
if dist[next_v] != -1:
if(dist[next_v]==dist[v]+1):
dp[next_v] += dp[v]
dp[next_v] %= m
continue
dist[next_v] = dist[v] + 1
dp[next_v] += dp[v]
dp[next_v] %= m
pre[next_v] = v
que.append(next_v)
return dist,pre,dp
def coordinates(A): # ( : ),2(: ),
B = sorted(set(A))
C = { v: i for i, v in enumerate(B) }
D = { i: v for i, v in enumerate(B) }
E = list(map(lambda v: C[v], A))
return C, D, E
def eng_L(): return list(string.ascii_lowercase)
def ENG_L(): return list(string.ascii_uppercase)
def idx_le(A, x): # x / "No"
return bisect_right(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"
def idx_lt(A, x): # x / "No"
return bisect_left(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"
def idx_ge(A, x): # x / "No"
return bisect_left(A, x) if bisect_left(A, x) != len(A) else "No"
def idx_gt(A, x): # x / "No"
return bisect_right(A, x) if bisect_right(A, x) != len(A) else "No"
def cnt_lt(A, x): # x
if(idx_lt(A, x) == "No"): return 0
return idx_lt(A, x) + 1
def cnt_le(A, x): # x
if(idx_le(A, x) == "No"): return 0
return idx_le(A, x) + 1
###/###
def MEX(A): #AMEX
A.sort()
if(A[0]!=0):
return 0
mex = 0
for i in range(1,len(A)):
if(A[i]==A[i-1]+1):
mex+=1
else:
break
return mex+1
def GCD(a,b): #ab
return math.gcd(a,b)
def LCM(a,b): #ab
return a*b//GCD(a,b)
def factorial(n, m=0): #n | m:mod()
if(n<0):
return -1
elif(n==0):
return 1
P = 1
for i in range(1,n+1):
P *= i
if(m==0):
continue
P %= m
return P
def nPr(n, r, m=0): #nPr
if(n<=0 or r<0 or n<r):
return -1
if(r==0):
return 1
P = 1
for i in range(n,n-r,-1):
P *= i
if(m==0):
continue
P %= m
return P
def nCr(n, r, m=0): #nCr
if(n<r):
return 0
if(n==r):
return 1
if(n<=0 or r<0 or n<r):
return -1
N = 1
for i in range(r):
N *= n-i
if(m==0):
continue
N %= m
R = factorial(r)
return N//R
def nCrm(n,r,m=mod): #nCr%mod
if(n<r):
return 0
if(n==r):
return 1
if(n<=0 or r<0 or n<r):
return -1
over=1
for i in range(n-r+1,n+1):
over *= i
over %= m
under=1
for i in range(1,r+1):
under *= i
under %= m
return over*pow(under,m-2,m)%m
def is_prime(n): # => True/False
if n == 2:
return 1
if n == 1 or n%2 == 0:
return 0
m = n - 1
lsb = m & -m
s = lsb.bit_length()-1
d = m // lsb
test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
for a in test_numbers:
if a == n:
continue
x = pow(a,d,n)
r = 0
if x == 1:
continue
while x != m:
x = pow(x,2,n)
r += 1
if x == 1 or r == s:
return 0
return 1
def prime_L(n): #n
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if not is_prime[i]:
continue
for j in range(i * 2, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
def find_prime_factor(n):
if n%2 == 0:
return 2
m = int(n**0.125)+1
for c in range(1,n):
f = lambda a: (pow(a,2,n)+c)%n
y = 0
g = q = r = 1
k = 0
while g == 1:
x = y
while k < 3*r//4:
y = f(y)
k += 1
while k < r and g == 1:
ys = y
for _ in range(min(m, r-k)):
y = f(y)
q = q*abs(x-y)%n
g = math.gcd(q,n)
k += m
k = r
r *= 2
if g == n:
g = 1
y = ys
while g == 1:
y = f(y)
g = math.gcd(abs(x-y),n)
if g == n:
continue
if is_prime(g):
return g
elif is_prime(n//g):
return n//g
else:
return find_prime_factor(g)
def primeFactorization_2L(n): #2n => [[, ], ...]2
if(n<=10**6):
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
else:
res = {}
while not is_prime(n) and n > 1:
p = find_prime_factor(n)
s = 0
while n%p == 0:
n //= p
s += 1
res[p] = s
if n > 1:
res[n] = 1
R = []
for r in res:
R.append([r,res[r]])
R.sort()
return R
def divisor_L(n): #n
if(n==1):
return [1]
if(n<=10**6):
lower_divisors , upper_divisors = [], []
i = 1
while i*i <= n:
if n % i == 0:
lower_divisors.append(i)
if i != n // i:
upper_divisors.append(n//i)
i += 1
return lower_divisors + upper_divisors[::-1]
else:
L = primeFactorization_2L(n)
E = [[]for i in range(len(L))]
for i in range(len(L)):
for j in range(L[i][1]+1):
E[i].append(L[i][0]**j)
D = []
for p in list(itertools.product(*E)):
s = 1
for v in p:
s *= v
D.append(s)
D.sort()
return D
def decimal_to_nAry(num_10,n): #10n(n<=10)
str_n = ''
while num_10:
if num_10%n>=10:
return -1
str_n += str(num_10%n)
num_10 //= n
return int(str_n[::-1])
def roundOff(x,d): # x:, d:(|) => float
return float(Decimal(x).quantize(Decimal(f"1E{d}"), rounding=ROUND_HALF_UP))
def dsin(d): #sin
return math.sin(math.radians(d))
def dcos(d): #cos
return math.cos(math.radians(d))
def rotate(x,y,d,cx=0,cy=0): #P(x,y)A(cx,cy) => [x,y]
nx = (x-cx)*dcos(d)-(y-cy)*dsin(d)
ny = (x-cx)*dsin(d)+(y-cy)*dcos(d)
return [nx+cx,ny+cy]
def findAngle(O,A,B): #∠AOB()
s = [A[0]-O[0],A[1]-O[1]]
t = [B[0]-O[0],B[1]-O[1]]
u = s[0]*t[0]+s[1]*t[1]
l = (s[0]**2+s[1]**2)**(1/2) * (t[0]**2+t[1]**2)**(1/2)
v = u/l
t = math.degrees(math.acos(v))
return t
def outerProduct(Av,Bv): #(=)(a×b)
return Av[0]*Bv[1] - Bv[0]*Av[1]
def CCW(O,A,B): #OAAB
# -1: , 0: , 1:
s = [A[0]-O[0],A[1]-O[1]]
t = [B[0]-O[0],B[1]-O[1]]
op = outerProduct(s,t)
if(op > 0): return 1
if(op < 0): return -1
if(op == 0): return 0
def matrixMultiplication_2D(a,b,m): #(a×b) m:mod
I,J,K,L = len(a),len(b[0]),len(b),len(a[0])
if(L!=K):
return -1
c = [[0] * J for _ in range(I)]
for i in range(I) :
for j in range(J) :
for k in range(K) :
c[i][j] += a[i][k] * b[k][j]
c[i][j] %= m
return c
def matrixExponentiation_2D(x,n,m): # (x^n) m:mod
y = [[0] * len(x) for _ in range(len(x))]
for i in range(len(x)):
y[i][i] = 1
while n > 0:
if n & 1:
y = matrixMultiplication_2D(x,y,m)
x = matrixMultiplication_2D(x,x,m)
n >>= 1
return y
def twoCircles(A,B): # | [x,y(=),r(=)]
# 1 : 2
# 2 : 2
# 3 : 2
# 4 : 2 2
# 5 : 2 2
x1 = A[0]
x2 = B[0]
y1 = A[1]
y2 = B[1]
r1 = A[2]
r2 = B[2]
d = abs((x1-x2)+1j*(y1-y2))
if(abs(r2-r1)>d):
return 1
elif(abs(r2-r1)==d):
return 2
elif(r1+r2>d):
return 3
elif(r1+r2==d):
return 4
elif(r1+r2<d):
return 5
######
def TS(_str): #/
print('{}: {}'.format(_str, eval(_str)))
def T2d(A): #
for a in A:
print(*a)
def BR(): #
print("---")
#----------------------------------------------------------------------
#-----------------------------------------------------------
'''
######
transpose(A): #
removeDuplicates_2D(A): #
cumulativeSum_1D(A) #A
cumulativeSum_2D(S): #S =>
string_to_runLength(S: str) #/ => [(,), ...]
runLength_to_string(L: "list[tuple]") # =>
bfs(i,m = mod): # i: m:mod(998244353) => dist,pre,dp
coordinates(A): # ( : ),2(: ),
eng_L() #
ENG_L() #
idx_le(A, x): # x / "No"
idx_lt(A, x): # x / "No"
idx_ge(A, x): # x / "No"
idx_gt(A, x): # x / "No"
cnt_lt(A, x): # x
cnt_le(A, x): # x
###/###
MEX(A) #AMEX
GCD(a,b) #ab
LCM(a,b) #ab
factorial(n,m) #n | m:mod()
nPr(n,r,m) #nPr | m:mod()
nCr(n,r,m) #,nCr | m:mod()
nCrm(n,r,m) #nCr%mod
divisor_L(n) #n
is_prime(n) # => True/False
prime_L(n) #n
primeFactorization_2L(n) #2n => [[, ], ...]2
decimal_to_nAry(num_10,n) #10n(n<=10)
roundOff(x,d): # x:, d:(|) => float
dsin(d): #sin
dcos(d): #cos
rotate(x,y,d,cx,cy): #P(x,y)A(cx,cy)() => [x,y]
findAngle(O,A,B) #∠AOB() | [x,y(=)]
outerProduct(Av,Bv) #(=)(a×b) | [x,y(=)]
CCW(O,A,B) #OAAB
=> -1:, 0:, 1: | [x,y(=)]
matrixMultiplication_2D(a,b,m) #(a×b) m:mod |
matrixExponentiation_2D(x,n m)# (x^n) m:mod |
twoCircles(A,B): # | [x,y(=),r(=)]
=> 1, 2, 3, 4, 5
######
TS(_str) #/ => :××
T2d(A): #
BR() #
'''
#PyPy----------------------------------
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
#----------------------------------------------------------------------------
s = SI()
bl = True
if(s[0]=="x"):
s = s[1:]
bl = False
s = int(s)
t = -(s-2**32)
if(bl):
print(s)
else:
print(t)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0