提出 #20838301
ソースコード 拡げる
import itertools
def area(x1, y1, x2, y2):
return (x2-x1) * (y2-y1)
def is_edge(j, pos):
if j == 0 or j == 1:
return pos <= 0
else:
return pos >= 10000
n = int(input())
ads = []
kans = []
xs = []
ys = []
for _j in range(n):
x, y, r = map(int, input().split())
ads.append([x, y, x+1, y+1, r, x, y])
kans.append([False, False, False, False])
xs.append(x)
ys.append(y)
ols = {}
for j in range(n):
ad = ads[j]
ox = list(filter(lambda p: p > ad[2], xs))
oox = list(map(lambda p: xs.index(p), ox))
oy = list(filter(lambda p: p > ad[3], ys))
ooy = list(map(lambda p: ys.index(p), oy))
ux = list(filter(lambda p: p < ad[0], xs))
uux = list(map(lambda p: xs.index(p), ux))
uy = list(filter(lambda p: p < ad[1], ys))
uuy = list(map(lambda p: ys.index(p), uy))
ols[j] = {'ox': oox, 'oy': ooy, 'ux': uux, 'uy': uuy}
while True:
for i in range(n):
oselistxs = []
oselistus = []
oselistoys = []
oselistuys = []
if all(kans[i]):
continue
if area(ads[i][0], ads[i][1], ads[i][2], ads[i][3]) >= ads[i][4]:
kans[i] = [True, True, True, True]
continue
for j in range(4):
if is_edge(j, ads[i][j]):
kans[i][j] = True
if (j == 0 or j == 1) and (ads[i][j] < 0):
ads[i][j] = 0
elif (j == 2 or j == 3) and (ads[i][j] > 10000):
ads[i][j] = 10000
for l in range(n):
if l == i:
continue
if not kans[i][0]:
uxf = False
if ads[l][2] == ads[i][0]-1 or ads[l][2] == ads[i][0]:
if ads[l][1] <= ads[i][1] <= ads[l][3]:
uxf = True
elif ads[l][1] <= ads[i][3] <= ads[l][3]:
uxf = True
elif ads[i][1] <= ads[l][1] and ads[i][3] >= ads[l][3]:
uxf = True
if uxf:
if kans[l][0] or kans[l][2]:
kans[i][0] = True
oselistxs = []
else:
oseruxf = True
for num in ols[l]['ux']:
if ads[num][2] == ads[l][0]:
if ads[num][1] <= ads[l][1] <= ads[num][3]:
oseruxf = False
break
elif ads[num][1] <= ads[l][3] <= ads[num][3]:
oseruxf = False
break
elif ads[num][1] <= ads[l][1] and ads[l][3] >= ads[num][3]:
oseruxf = False
break
if ads[l][2] <= ads[l][5]+1:
oseruxf = False
if is_edge(0, ads[l][0]):
oseruxf = False
if oseruxf:
oselistxs.append(l)
else:
oselistxs = []
kans[i][0] = True
if not kans[i][1]:
uyf = False
if ads[l][3] == ads[i][1]-1 or ads[l][3] == ads[i][1]:
if ads[l][0] <= ads[i][0] <= ads[l][2]:
uyf = True
elif ads[l][0] <= ads[i][2] <= ads[l][2]:
uyf = True
elif ads[i][0] <= ads[l][0] and ads[i][2] >= ads[l][2]:
uyf = True
if uyf:
if kans[l][3] or kans[l][1]:
kans[i][1] = True
oselistoys = []
else:
oseruoyf = True
for num in ols[l]['uy']:
if ads[num][3] == ads[l][1]:
if ads[num][0] <= ads[l][0] <= ads[num][2]:
oseruoyf = False
break
elif ads[num][0] <= ads[l][2] <= ads[num][2]:
oseruoyf = False
break
elif ads[l][0] <= ads[num][0] and ads[l][2] >= ads[num][2]:
oseruoyf = False
break
if ads[l][3] <= ads[l][6]+1:
oseruoyf = False
if is_edge(1, ads[l][1]):
oseruxf = False
if oseruoyf:
oselistoys.append(l)
else:
oselistoys = []
kans[i][1] = True
if not kans[i][2]:
oxf = False
if ads[l][0] == ads[i][2]+1 or ads[l][0] == ads[i][2]:
if ads[l][1] <= ads[i][1] <= ads[l][3]:
oxf = True
elif ads[l][1] <= ads[i][3] <= ads[l][3]:
oxf = True
elif ads[i][1] <= ads[l][1] and ads[i][3] >= ads[l][3]:
oxf = True
if oxf:
if kans[l][0] or kans[l][2]:
kans[i][2] = True
oselistus = []
else:
oseruuxf = True
for num in ols[l]['ox']:
if ads[num][0] == ads[l][2]:
if ads[num][1] <= ads[l][1] <= ads[num][3]:
oseruuxf = False
break
elif ads[num][1] <= ads[l][3] <= ads[num][3]:
oseruuxf = False
break
elif ads[num][1] <= ads[l][1] and ads[l][3] >= ads[num][3]:
oseruuxf = False
break
if ads[l][0] >= ads[l][5]-1:
oseruuxf = False
if is_edge(2, ads[l][2]):
oseruxf = False
if oseruuxf:
oselistus.append(l)
else:
oselistus = []
kans[i][2] = True
if not kans[i][3]:
oyf = False
if ads[l][1] == ads[i][3]+1 or ads[l][1] == ads[i][3]:
if ads[l][0] <= ads[i][0] <= ads[l][2]:
oyf = True
elif ads[l][0] <= ads[i][2] <= ads[l][2]:
oyf = True
elif ads[i][0] <= ads[l][0] and ads[i][2] >= ads[l][2]:
oyf = True
if oyf:
if kans[l][3] or kans[l][1]:
kans[i][3] = True
oselistuys = []
else:
oseruuyf = True
for num in ols[l]['oy']:
if ads[num][1] == ads[l][3]:
if ads[num][0] <= ads[l][0] <= ads[num][2]:
oseruuyf = False
break
elif ads[num][0] <= ads[l][2] <= ads[num][2]:
oseruuyf = False
break
elif ads[l][0] <= ads[num][0] and ads[l][2] >= ads[num][2]:
oseruuyf = False
break
if ads[l][1] >= ads[l][6]-1:
oseruuyf = False
if is_edge(3, ads[l][3]):
oseruxf = False
if oseruuyf:
oselistuys.append(l)
else:
oselistuys = []
kans[i][3] = True
for t in range(4):
if not kans[i][t]:
if t == 0 or t == 1:
ads[i][t] -= 1
else:
ads[i][t] += 1
for osexs in oselistxs:
ads[osexs][0] -= 1
ads[osexs][2] -= 1
if ads[osexs][0] < 0:
ads[osexs][0] = 0
for oseus in oselistus:
ads[oseus][0] += 1
ads[oseus][2] += 1
if ads[oseus][2] > 10000:
ads[oseus][2] = 10000
for oseoys in oselistoys:
ads[oseoys][1] -= 1
ads[oseoys][3] -= 1
if ads[oseoys][1] < 0:
ads[oseoys][1] = 0
for oseuys in oselistuys:
ads[oseuys][1] += 1
ads[oseuys][3] += 1
if ads[oseuys][3] > 10000:
ads[oseuys][3] = 10000
if all(list(itertools.chain.from_iterable(kans))):
break
for i in range(n):
print(ads[i][0], ads[i][1], ads[i][2], ads[i][3])
提出情報
| 提出日時 | |
|---|---|
| 問題 | A - AtCoder Ad |
| ユーザ | yougoto |
| 言語 | PyPy3 (7.3.0) |
| 得点 | 0 |
| コード長 | 10060 Byte |
| 結果 | WA |
| 実行時間 | 1564 ms |
| メモリ | 85812 KiB |
ジャッジ結果
| セット名 | test_ALL | ||||
|---|---|---|---|---|---|
| 得点 / 配点 | 0 / 50000000000 | ||||
| 結果 |
|
| セット名 | テストケース |
|---|---|
| test_ALL | test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt |
| ケース名 | 結果 | 実行時間 | メモリ |
|---|---|---|---|
| test_0000.txt | AC | 604 ms | 76424 KiB |
| test_0001.txt | AC | 914 ms | 81424 KiB |
| test_0002.txt | WA | 783 ms | 81680 KiB |
| test_0003.txt | AC | 1564 ms | 85736 KiB |
| test_0004.txt | AC | 894 ms | 80184 KiB |
| test_0005.txt | AC | 813 ms | 80120 KiB |
| test_0006.txt | AC | 914 ms | 81568 KiB |
| test_0007.txt | AC | 917 ms | 82392 KiB |
| test_0008.txt | AC | 1178 ms | 79872 KiB |
| test_0009.txt | AC | 883 ms | 79920 KiB |
| test_0010.txt | WA | 882 ms | 81704 KiB |
| test_0011.txt | AC | 875 ms | 81824 KiB |
| test_0012.txt | AC | 1135 ms | 81668 KiB |
| test_0013.txt | AC | 725 ms | 78936 KiB |
| test_0014.txt | AC | 1036 ms | 79748 KiB |
| test_0015.txt | AC | 1191 ms | 83508 KiB |
| test_0016.txt | AC | 1254 ms | 81592 KiB |
| test_0017.txt | WA | 1298 ms | 85720 KiB |
| test_0018.txt | AC | 1060 ms | 82164 KiB |
| test_0019.txt | AC | 1097 ms | 83128 KiB |
| test_0020.txt | AC | 739 ms | 79560 KiB |
| test_0021.txt | AC | 1110 ms | 83240 KiB |
| test_0022.txt | AC | 641 ms | 78052 KiB |
| test_0023.txt | AC | 939 ms | 81900 KiB |
| test_0024.txt | AC | 1040 ms | 82724 KiB |
| test_0025.txt | AC | 1114 ms | 83776 KiB |
| test_0026.txt | AC | 1193 ms | 83788 KiB |
| test_0027.txt | AC | 1450 ms | 85812 KiB |
| test_0028.txt | AC | 819 ms | 81284 KiB |
| test_0029.txt | AC | 888 ms | 84308 KiB |
| test_0030.txt | AC | 794 ms | 80084 KiB |
| test_0031.txt | AC | 884 ms | 81876 KiB |
| test_0032.txt | AC | 754 ms | 79244 KiB |
| test_0033.txt | WA | 1406 ms | 82776 KiB |
| test_0034.txt | AC | 1241 ms | 83948 KiB |
| test_0035.txt | WA | 908 ms | 80664 KiB |
| test_0036.txt | AC | 695 ms | 78880 KiB |
| test_0037.txt | AC | 866 ms | 80160 KiB |
| test_0038.txt | AC | 860 ms | 82164 KiB |
| test_0039.txt | AC | 1243 ms | 82880 KiB |
| test_0040.txt | WA | 1312 ms | 83840 KiB |
| test_0041.txt | AC | 1052 ms | 83868 KiB |
| test_0042.txt | AC | 1067 ms | 82352 KiB |
| test_0043.txt | AC | 729 ms | 80204 KiB |
| test_0044.txt | WA | 1390 ms | 82528 KiB |
| test_0045.txt | AC | 1100 ms | 79544 KiB |
| test_0046.txt | AC | 1213 ms | 80920 KiB |
| test_0047.txt | WA | 1061 ms | 79196 KiB |
| test_0048.txt | AC | 1068 ms | 81484 KiB |
| test_0049.txt | AC | 1091 ms | 79508 KiB |