結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-26 16:04:08 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 481 ms / 1,000 ms |
コード長 | 2,251 bytes |
コンパイル時間 | 15,403 ms |
実行使用メモリ | 8,356 KB |
スコア | 30,973 |
最終ジャッジ日時 | 2018-05-26 16:04:25 |
ジャッジサーバーID (参考情報) |
judge9 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
# coding: utf-8# import timeimport randomfrom heapq import heappush,heappopdef evalute(grid):return sum([r.count(0) for r in grid])def operation_grid(op, grid):rev_grid = gridif op[1] == op[3]:length = op[2] - op[0] + 1for i in range(length):rev_grid[op[0]-1+i][op[1]-1] = (grid[op[0]-1+i][op[1]-1]+1)&1if op[0] == op[2]:length = op[3] - op[1] + 1for i in range(length):rev_grid[op[0]-1][op[1]-1+i] = (grid[op[0]-1][op[1]-1+i]+1)&1return rev_griddef count_black_horizon(grid, base_x, base_y, length):return grid[base_y][base_x:base_x + length].count(1)def count_black_vertical(grid, base_x, base_y, length):return [grid[i][base_x] for i in range(base_y,base_y + length)].count(1)# begin = time.time()N,K = map(int,input().split())L = list(map(int,input().split()))A = [list(map(int,list(input()))) for i in range(N)]operation = []P = 100for k in range(K):hq = []for i in range(P):x = random.randint(0, N-L[k])y = random.randint(0, N-L[k])horizon_cnt = count_black_horizon(A, x, y, L[k])vertical_cnt = count_black_vertical(A, x, y, L[k])# print(horizon_cnt,end=" ")# print(vertical_cnt)if horizon_cnt < vertical_cnt:heappush(hq, (-vertical_cnt, [y+1, x+1, y+L[k], x+1]))else:heappush(hq, (-horizon_cnt, [y+1, x+1, y+1, x+L[k]]))# for x in range(N-L[k]+1):# for y in range(N-L[k]+1):# horizon_cnt = count_black_horizon(A, x, y, L[k])# vertical_cnt = count_black_vertical(A, x, y, L[k])# # print(horizon_cnt,end=" ")# # print(vertical_cnt)# if horizon_cnt < vertical_cnt:# heappush(hq, (-vertical_cnt, [y+1, x+1, y+L[k], x+1]))# else:# heappush(hq, (-horizon_cnt, [y+1, x+1, y+1, x+L[k]]))cnt, op = heappop(hq)A = operation_grid(op, A)operation.append(op)best_score = evalute(A)print('\n'.join([' '.join(list(map(str,op))) for op in operation]))# print('best_score = ' + str(best_score))# print('----END----')# take = time.time() - begin# print(str(round(int(take * 1000),3)) + " ms")