結果
| 問題 | No.5022 XOR Printer |
| コンテスト | |
| ユーザー |
 ra5anchor
|
| 提出日時 | 2025-07-31 12:33:02 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 169 ms / 2,000 ms |
| コード長 | 6,100 bytes |
| コンパイル時間 | 266 ms |
| コンパイル使用メモリ | 82,172 KB |
| 実行使用メモリ | 82,812 KB |
| スコア | 5,175,380,292 |
| 最終ジャッジ日時 | 2025-07-31 12:33:13 |
| 合計ジャッジ時間 | 10,824 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import copy
import random
from time import perf_counter
import argparse
import sys
import math
MAX = 10**8
class TimeKeeper:
def __init__(self):
self.start_time = perf_counter()
def is_time_over(self, LIMIT):
return (perf_counter() - self.start_time) >= LIMIT
def time_now(self):
return (perf_counter() - self.start_time)
###########################################
def main(DEBUG):
tk = TimeKeeper()
if DEBUG == True:
LIMIT = 0.3
else:
LIMIT = 1.7
def cal_score(A):
N = 10
score = 0
for i in range(N):
for j in range(N):
score += A[i][j]
return score
def cal_score_sim(ANS):
N = 10
nowi = 0
nowj = 0
s = 0
B = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
B[i][j] = A[i][j]
if len(ANS) > 1000:
return -1
for c in ANS:
if c == "L":
nowj -= 1
elif c == "R":
nowj += 1
elif c == "U":
nowi -= 1
elif c == "D":
nowi += 1
elif c == "W":
B[nowi][nowj] ^= s
elif c == "C":
s ^= B[nowi][nowj]
if nowi < 0 or nowi >= N or nowj < 0 or nowj >= N:
return -1
score = 0
for i in range(N):
for j in range(N):
score += B[i][j]
return score
def goto(nowi, nowj, toi, toj):
res = []
di = toi - nowi
dj = toj - nowj
if di > 0:
for _ in range(di):
res.append("D")
else:
for _ in range(abs(di)):
res.append("U")
if dj > 0:
for _ in range(dj):
res.append("R")
else:
for _ in range(abs(dj)):
res.append("L")
return res
def get_order(w_pos, nowi, nowj):
# greedy
w = []
while len(w_pos)>0:
w_pos.sort(key=lambda x: -abs(x[0]-nowi)-abs(x[1]-nowj))
(toi, toj) = w_pos.pop()
w.append((toi, toj))
nowi = toi
nowj = toj
return w
def get_order2(w_pos):
# zigzag
idx = dict()
cnt = 0
for i in range(N):
if i%2==0:
for j in range(N):
idx[(i,j)] = cnt
cnt += 1
else:
for j in reversed(range(N)):
idx[(i,j)] = cnt
cnt += 1
w_pos.sort(key=lambda x: idx[x[0],x[1]])
return w_pos
def solve():
X = [[0]*N for _ in range(N)]
for i in range(N):
for j in range(N):
X[i][j] = A[i][j]
nowi = 0
nowj = 0
s = 0
actions = []
for k in range(20): # k:keta
# sを設定する
xnow = s >> 20-1-k & 1
kouho = []
for i in range(N):
for j in range(N):
# if (X[i][j] >> (20-1-k)) & 1 == 1:
if (X[i][j] >> 20-1-k+1 == (1 << k) - 1) and (X[i][j] >> 20-1-k & 1 == 1-xnow):
ti, tj = i, j
d = abs(nowi-i) + abs(nowj-j)
kouho.append((d, ti, tj))
kouho.sort()
if len(kouho)==0:
print(f"not found kouho {k=} -> break", file=sys.stderr)
break
d, ti, tj = kouho[0]
# 目的地へ向かう
res = goto(nowi, nowj, ti, tj)
actions.extend(res)
nowi = ti
nowj = tj
# Copyして完成
actions.append("C")
s ^= X[nowi][nowj]
# 書き込みする地点列挙
w_pos = []
for i in range(N):
for j in range(N):
# if (X[i][j] >> (20-1-k)) & 1 == 0:
if (X[i][j] >> 20-1-k+1 == (1 << k) - 1) and (X[i][j] >> 20-1-k & 1 == 0):
w_pos.append((i, j))
if len(w_pos) == 0:
print(f"not found w_pos {k=} -> break", file=sys.stderr)
break
mxv = 0
for (toi, toj) in w_pos:
v = X[toi][toj]
if v > mxv:
mxv = v
mxi, mxj = toi, toj
w_pos.remove((mxi, mxj))
# 巡回する順番決め
w_pos_ordered = get_order(w_pos, nowi, nowj)
# w_pos_ordered = get_order2(w_pos)
# 一つ残して巡回
for (toi, toj) in w_pos_ordered:
res = goto(nowi, nowj, toi, toj)
actions.extend(res)
nowi = toi
nowj = toj
# Print
actions.append("W")
X[nowi][nowj] ^= s
# 最後の一つはsに書き込む
toi, toj = mxi, mxj
res = goto(nowi, nowj, toi, toj)
actions.extend(res)
nowi = toi
nowj = toj
# Copy
actions.append("C")
s ^= X[nowi][nowj]
print(f"{k=} skip ({nowi} {nowj}) turn {len(actions)}", file=sys.stderr)
print(f"{k=} {s=} {bin(s)=}", file=sys.stderr)
print(X, file=sys.stderr)
return actions
N, T = map(int, input().split())
# N=10, T=1000
A = [list(map(int, input().split())) for _ in range(N)]
ANS = solve()
print(f"T: {len(ANS)}", file=sys.stderr)
ANS = ANS[:T]
sc = cal_score_sim(ANS)
print(f"SC: {sc}", file=sys.stderr)
print(*ANS, sep='\n')
if __name__ == '__main__':
parser = argparse.ArgumentParser(description='Debug mode')
parser.add_argument('--debug', action='store_true', help='Enable debug mode')
args = parser.parse_args()
main(args.debug)