結果
| 問題 |
No.1945 Go Push!
|
| コンテスト | |
| ユーザー |
 sanao10000
|
| 提出日時 | 2022-05-20 23:26:52 |
| 言語 | Nim (2.2.0) |
| 結果 |
AC
|
| 実行時間 | 45 ms / 2,000 ms |
| コード長 | 11,793 bytes |
| コンパイル時間 | 3,867 ms |
| コンパイル使用メモリ | 91,716 KB |
| 実行使用メモリ | 18,224 KB |
| 最終ジャッジ日時 | 2024-09-20 09:53:21 |
| 合計ジャッジ時間 | 5,183 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 |
コンパイルメッセージ
/home/judge/data/code/Main.nim(5, 40) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated] /home/judge/data/code/Main.nim(5, 5) Warning: imported and not used: 'sugar' [UnusedImport] /home/judge/data/code/Main.nim(5, 40) Warning: imported and not used: 'future' [UnusedImport] /home/judge/data/code/Main.nim(5, 21) Warning: imported and not used: 'bitops' [UnusedImport]
ソースコード
{.passc: "-std=gnu++17 -Wall -Wextra -O2 -DONLINE_JUDGE -I/opt/boost/gcc/include -L/opt/boost/gcc/lib -I/opt/ac-library".}
{.optimization:speed.}
import strformat, macros, std/algorithm, tables, sets, lists,
intsets, critbits, sequtils, strutils, std/math, times,
sugar, options, bitops, heapqueue, future, std/deques
proc powMod*(a, b, c: int): int {.importcpp: "atcoder::pow_mod(#, @)", header: "<atcoder/all>".}
proc po*(a: int): int {.importcpp: "std::fgets(#)", header: "<cstdio>".}
const
MOD = 1000000007
MOD_ANOTHER = 998244353
# 入力テンプレ-------------------------------------------------
proc g(): string = stdin.readLine
proc gin(): int = g().parseInt
proc gInts(): seq[int] = g().split.map(parseInt)
proc gIntsN(n:int): seq[int] =
result=newSeq[int](n)
for i in 0..n-1:result[i]=gin()
proc gIntsNs(n:int): seq[seq[int]] =
result=newSeq[seq[int]](n)
for i in 0..n-1:result[i]=gInts()
proc gStrN(n:int): seq[string] =
result = newSeq[string](n)
for i in 0..n-1:result[i]=g()
# ----------------------------------------------------------------
template last(a:untyped): untyped = a[a.len - 1]
func head(a:openarray[int]):Option[int] =
if(a.len > 0):a[0].some else:int.none
func head(a:openarray[float]):Option[float] =
if(a.len > 0):a[0].some else:float.none
func head(a:openarray[string]):Option[string] =
if(a.len > 0):a[0].some else:string.none
template `tail` (a:typed):untyped = a[1..len(a)-1]
template `init` (a:typed):untyped = a[0..len(a)-2]
template `&&`(a,b:untyped):untyped =
if(a==true and b==true):true else: false
template `||`(a,b:untyped):untyped =
if(a==true or b==true):true else: false
func chmax[T](n: var T, m: T) {.inline.} = n = max(n, m)
func chmin[T](n: var T, m: T) {.inline.} = n = min(n, m)
func plus[T](a,b:T):T=return a+b
func product[T](a:openArray[T]):T=
result=1
for i in a:result = result * i
func subtract[T](a,b:T):T=return a-b
func zipwith[T1,T2,T3](f: proc(a:T1,b:T2):T3, xs:openarray[T1],ys:openarray[T2]): seq[T1] =
newSeq(result, xs.len)
for i in low(xs)..high(xs): result[i] = f(xs[i],ys[i])
proc zip3[S,T,U](a:seq[S],b:seq[T],c:seq[U]):seq[(S,T,U)]=
for i in zip(zip(a,b),c):result.add((i[0][0],i[0][1],i[1]))
func search[T](x:seq[T],y:T) : bool =
for i in x:
if i == y : return true
return false
func `++`[T](a:T):T = a+1
func `--`[T](a:T):T = a-1
func Qsort[T](x:seq[T]):seq[T] =
if(x.len<=1):return x
else:
var
pivot = x[0]
left:seq[T] = @[]
right:seq[T] = @[]
for i in 1..<x.len:
if(x[i]<pivot):add(left,x[i])
else:add(right,x[i])
return Qsort(left) & @[pivot] & Qsort(right)
func partialSort[T](List:seq[T],left:T,right:T):seq[T] =
var sortedZone:seq[T] = List[left - 1..right - 1].Qsort()
return List[0..left - 2] & sortedZone & List[right .. List.len - 1]
proc rotR(a:char):char =
var b=ord a
if(b==122):return chr(97)
else:return chr(++b)
proc rotL(a:char):char =
var b=ord a
if(b==97):return chr(122)
else:return chr(--b)
proc msi():seq[int]=newSeq[int]()
func transepose(arr:seq[seq[int]]):seq[seq[int]] =
var
hight=arr.len
width=arr.mapIt(it.len)[0]
result=newSeq[seq[int]]()
for i in 0..<width:
var tmpArr=msi()
for j in 0..<hight:
tmpArr.add(arr[j][i])
result.add(tmpArr)
func transepose(arr:seq[string]):seq[string] =
var
hight=arr.len
width=arr.mapIt(it.len)[0]
var res=newSeq[seq[char]]()
for i in 0..<width:
var tmpArr=newSeq[char]()
for j in 0..<hight:
tmpArr.add(arr[j][i])
res.add(tmpArr)
return res.mapIt(it.join())
proc toInt(c:char): int = return int(c) - int('0')
# 配列埋め----------------------------------------------------------
func makeSeqNums[T](height:int,width:int,fille:T):seq[seq[T]] =
result = newSeqWith(height, newSeq[T](width))
for i in 0..<height:
for j in 0..<width:
result[i][j]=fille
#グラフ関連------------------------------------------------------------
proc makeUndirectGraph(arr:seq[seq[int]],n:int):seq[seq[int]] =
result=newSeq[seq[int]](n)
var a,b:int
for i in arr:
(a,b)=(i[0]-1,i[1]-1)
result[a].add(b)
result[b].add(a)
proc makeDirectGraph(arr:seq[seq[int]],n:int):seq[seq[int]] =
result=newSeq[seq[int]](n)
var a,b:int
for i in arr:
(a,b)=(i[0]-1,i[1]-1)
result[a].add(b)
func path(arr:seq[seq[int]],n:int):seq[seq[bool]] =
result=newSeq[seq[bool]]()
for i in 0..<n:result.add(newSeqWith(n,false))
for i in arr:
result[i[0]-1][i[1]-1]=true
result[i[1]-1][i[0]-1]=true
proc makeDiGraphWithCost[T](arr:seq[seq[T]],n:int):seq[seq[(int,T)]] =
result=newSeq[seq[(int,int)]](n)
for inp in arr:result[inp[0]].add((inp[1]-1.int,inp[2]))
proc makeUnGraphWithCost(arr:seq[seq[int]],n:int):seq[seq[(int,int)]] =
result=newSeq[seq[(int,int)]](n)
for inp in arr:
result[inp[0]-1].add((inp[1]-1,inp[2]))
result[inp[1]-1].add((inp[0]-1,inp[2]))
template isemptyQ(a:typed):untyped =
if(a.len==0):true
else:false
#ダイクストラ
proc dijkstra(arr:seq[seq[(int,int)]],start:int,n:int):seq[int] =
var
heap = initHeapQueue[(int,int)]()
cost=newSeqWith(n,-1)
done=newSeqWith(n,false)
heap.push((0,start))
cost[start] = 0
while(not(heap.isemptyQ)):
var(co,pos)=heap.pop()
if(done[pos]):continue
done[pos] = true
for (i,d) in arr[pos]:
if (cost[i] == -1 or cost[i] > cost[pos] + d):
cost[i] = d + cost[pos]
heap.push((cost[i],i))
return cost
#幅優先探索
func bfs(G:seq[seq[int]],n:int,start:int):(seq[int],seq[int]) =
var
dist = newSeqWith(n,-1)
que = initDeque[int]()
prev = newSeqWith(n,-1)
dist[start] = 0
que.addLast(start)
while(not(que.isemptyQ)):
var v = que.popFirst()
for nv in G[v]:
if(dist[nv] != -1):continue
dist[nv] = dist[v] + 1
prev[nv] = v
que.addLast(nv)
return (dist,prev)
#迷路探索
proc mazeBFS(R,C,sy,sx,gy,gx:int,field:seq[string],wall:char):int=
var
dist=makeSeqNums(R,C,-1)
que=initDeque[(int,int)]()
que.addLast((sy,sx))
dist[sy][sx]=0
while(not(que.isemptyQ)):
var(ny,nx)=que.popFirst()
for (i2,j2) in ([[ny+1,nx],[ny-1,nx],[ny,nx+1],[ny,nx-1]]):
if(not((i2>=0 and i2 < R) and (j2 >= 0 and j2 < C))):continue
if(field[ny][nx]==wall):continue
if(dist[i2][j2] == -1):
dist[i2][j2]=dist[ny][nx] + 1
que.addLast((i2,j2))
return dist[gy][gx]
# ------------------------------------------------------------------
#union-find
type UnionFind = ref object
parent:seq[int]
rank:seq[int]
proc makeUf(n:int):UnionFind =
result=UnionFind(parent:newSeq[int](n),rank:newSeq[int](n))
for i in 0..<n:result.parent[i] = -1
for i in 0..<n:result.rank[i] = 1
proc rootUf(uf:UnionFind; x: int):int =
if (uf.parent[x] == -1):return x
uf.parent[x] = uf.rootUf(uf.parent[x])
return uf.parent[x]
proc uniteUf(uf:UnionFind,x,y:int):void =
var
a=rootUf(uf,x)
b=rootUf(uf,y)
if(a == b):return
if(uf.rank[a]>uf.rank[b]):swap(a,b)
if(uf.rank[a]==uf.rank[b]):uf.rank[b] += 1
uf.parent[a]=b
proc sameUf(uf:UnionFind,x,y:int):bool =
return if(uf.rootUf(x) == uf.rootUf(y)):true else: false
proc sizeUf(uf:UnionFind,a:int):int =
- uf.parent[uf.rootUf(a)]
#----------------------------------------------------------
#binary indexed tree
type Bit = ref object
size:int
tree:seq[int]
proc initBit(n:int):Bit =
result = Bit(size:n,tree:newSeqWith(n+1,0))
proc sumBit(bit:Bit,i:int):int =
result=0
var k = i
k -= 1
while(k>=0):
result += bit.tree[k]
k = (k and (k+1)) - 1
proc addBit(bit:Bit,i:int,x:int):void =
var k = i
while(k < bit.size):
bit.tree[k] += x
k = (k or (k+1))
proc rangeBit(bit:Bit,l:int,r:int):int =
if(l==0):return bit.sumBit(r)
return bit.sumBit(r) - bit.sumBit(l)
proc buildBit(bit:Bit,arr:seq[int]):Bit=
for ix,i in arr:bit.addBit(ix,i)
return bit
proc makeBit(arr:seq[int],n:int):Bit =
return initBit(n).buildBit(arr)
#----------------------------------------------------------
#累積和
func cumsum[T](m:seq[T],n:int):seq[T] =
var zero:T = 0
result : seq[T] = newSeqWith(n+1,zero)
for i in 0..<n:result[i+1]=result[i]+m[i]
# 約数列挙
func divisors(num:int):seq[int] =
result=newSeq[int]()
for i in countup(1,toInt(pow(toFloat(num),0.5))):
if num mod i != 0:continue
result.add(i)
if((num div i) != i):result.add((num div i))
result.sort()
#素数判定
func isPrime(num:int):bool =
if(num <= 1): return false
else:
for i in countup(2,toInt(pow(toFloat(num),0.5))):
if(num mod i == 0):
return false
return true
#素数列挙
func primeRekkyo(n:int):seq[int] =
for i in 0..n:
if(isPrime(i)):result.add(i)
# 素因数分解
func primeFactorization(n:var int):seq[int]=
var i:int=2
while i<=int sqrt(float n):
if n.mod(i)!=0:i+=1
else:
n=n.div(i)
result.add(i)
if n!=1:result.add(n)
#エラトスネテスの篩
func Erat(N:int):seq[int] =
var isprime = newSeqWith(N+1,true)
isprime[0] = false
isprime[1] = false
for p in 2..<N+1:
if not isprime[p]:continue
var q = p * 2
while q <= N:
isprime[q] = false
q += p
return(zip((tail isprime),(1..N).toSeq)).filterIt(it[0]==true).mapIt(it[1])
#順列全探索用 quoted from "https://forum.nim-lang.org/t/2812"
proc perm[T](a: openarray[T], n: int, use: var seq[bool]): seq[seq[T]] =
result = newSeq[seq[T]]()
if n <= 0: return
for i in 0 .. a.high:
if not use[i]:
if n == 1:result.add(@[a[i]])
else:
use[i] = true
for j in perm(a, n - 1, use):result.add(a[i] & j)
use[i] = false
proc permutations[T](a: openarray[T], n: int = a.len): seq[seq[T]] =
var use = newSeq[bool](a.len)
perm(a, n, use)
proc nCr(n:int,r:int):int =
if(r==0 or r==n):return 1
else:
return nCr(n-1,r-1) + nCr(n-1,r)
#itertools
iterator prod[T](s: openArray[T], repeat: Positive): seq[T] =
var counters = newSeq[int](repeat)
block outer:
while true:
var result = newSeq[T](repeat)
for i, cnt in counters:
result[i] = s[cnt]
yield result
var i = repeat - 1
while true:
inc counters[i]
if counters[i] == s.len:
counters[i] = 0
dec i
else: break
if i < 0:break outer
iterator groupC[T](s: openArray[T]): tuple[k: T, v: seq[T]] =
var
k = s[0]
v = @[k]
i = 1
while i < s.len:
if s[i] != k:
yield (k, v)
k = s[i]
v = @[k]
else:
v.add k
inc i
yield (k, v)
iterator groupC[T, U](s: openArray[T], f: proc(a: T): U): tuple[k: U, v: seq[T]] =
var
k = f(s[0])
v = @[s[0]]
i = 1
while i < s.len:
let fx = f(s[i])
if fx != k:
yield (k, v)
k = fx
v = @[s[i]]
else:
v.add s[i]
inc i
yield (k, v)
#itertools end--------------------------------------------
proc group[T](s:seq[T]):seq[seq[T]] =
var res = newSeq[seq[T]]()
for (k,v) in groupC(s):res.add(v)
return res
# compress
func compress[T](arr:seq[T]):seq[T]=
var
c:seq[T] = arr.toHashSet().toSeq().sorted()
zero:T = 0
res = newSeqWith(arr.len,zero)
for i in 0..<arr.len:
res[i]= c.lowerBound(arr[i],system.cmp[int])
return res
#tuple sort
proc sortFst[T, U](arr:seq[tuple[fst:T,snd:U]]):seq[(T,U)] = arr.sortedByIt(it.fst).mapIt((it.fst,it.snd))
proc sortSnd[T, U](arr:seq[tuple[fst:T,snd:U]]):seq[(T,U)] = arr.sortedByIt(it.snd).mapIt((it.fst,it.snd))
# main処理----------------------------------------------------------
proc main() =
var
n=gin()
A=gInts()
if(n mod 2 != 0):
echo "First"
else:
echo "Second"
when isMainModule:
main()