故事
高桥市目前正在建设一座新的废物处理设施。 各种类型的废物将被带入该设施,因此在处理前必须对其进行分类。 可以使用多种类型的设备进行分类,例如使用磁铁将含铁的物品与其他物品分开。 然而,分拣机按概率将废物分配到两条路径中,并且无法准确识别废物的类型。 因此,需要适当组合多种分拣机,例如先按形状将易拉罐与其他物品分离,然后利用磁铁将铝罐与钢罐分离。 通过有效组合多个分拣机,尽可能准确地进行垃圾分类。
问题陈述
正在建设废物处理设施,以进行处理和分类 N 废物类型。 该设施表示为 2D 平面上的正方形区域,其中 0\leq x\leq 10^4 和 0\leq y\leq 10^4。 各种类型的废物将通过 废物入口,并通过安装 处理器 和 分拣机 通过连接 传送带,目的是在处理前尽可能准确地对废物进行分类。
废物入口
设施内只有一个废物入口,位于坐标处 (0,5000)。 一条传送带从入口延伸,将废物运送到处理器或分类器。
处理器
为每种类型的废物安装一个处理器。 目标是将每种类型的废物输送到正确的处理器。
正好有 N 设施内可以安装处理器的位置,以及处理器的坐标 i-第位置是 (x^d_i,y^d_i)。 您可以自由指定在每个位置安装哪种类型的废物处理器。
分拣机
有 K 自动垃圾分类机的类型。 同一分拣机可以安装在多个位置。
每个分拣机有可能将传入的废物路由到两条路径之一,通过出口 1 或出口 2 排出。 的概率 i-th 分拣机路由类型废物 j 到出口 1 是 p_{i,j},到达出口 2 的概率为 1-p_{i,j}.
有 M 设施内可用于安装分拣机的位置,以及分拣机的坐标 i-第位置是 (x^s_i,y^s_i)。 每个地点最多可安装一台分拣机。
输送带
传送带必须从废物入口和分拣机的两个出口中延伸,以将废物输送到处理器或另一个分拣机。 每条传送带均铺设为连接起点和终点的线段,并且不共享任何端点的两条传送带不得相交。 在这种情况下,允许分拣机的两个出口指向同一目的地。
考虑有向图,其中废物入口、处理器和分类器是顶点,传送带是边,该图不得包含任何循环(包括自循环)。
提示:线段相交检测
判断两条线段是否 p_1p_2 和 q_1q_2 分享任何一点,使用以下伪代码。 由于所有计算值都是整数,因此不会发生舍入错误。
def sign(x):
return 1 if x > 0 else -1 if x < 0 else 0
def orientation(a, b, c):
cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
return sign(cross)
def segments_intersect(p1, p2, q1, q2):
if (max(p1.x, p2.x) < min(q1.x, q2.x) or
max(q1.x, q2.x) < min(p1.x, p2.x) or
max(p1.y, p2.y) < min(q1.y, q2.y) or
max(q1.y, q2.y) < min(p1.y, p2.y)):
return False
o1 = orientation(p1, p2, q1)
o2 = orientation(p1, p2, q2)
o3 = orientation(q1, q2, p1)
o4 = orientation(q1, q2, p2)
return (o1 * o2 <= 0) and (o3 * o4 <= 0)
分数
让 q_i 是类型浪费的概率 i 最终被传递到其相应的处理器。 然后,授予以下绝对分数:
\[ \mathrm{round}\left(10^9\times \frac{1}{N}\sum_{i=0}^{N-1}(1-q_i)\right) \]
绝对分数越低越好。
对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的绝对分数,MIN 是在该测试用例中获得的所有竞争对手中最低的绝对分数。提交的分数是相对分数的总和。
最终排名将通过比赛结束后进行的系统测试进行更多的输入来确定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。
系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。
测试用例数量
- 临时测试:50
- 系统测试:2000年。我们将发布 种子.txt (sha256=b61fb5678d480a79e25a50141403e14e8e245d5699e90aa53d4fad893e10dee8) 比赛结束后。
关于相关评价体系
在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。
输入
输入由标准输入按以下格式给出。
N M K
x^d_0 y^d_0
\vdots
x^d_{N-1} y^d_{N-1}
x^s_0 y^s_0
\vdots
x^s_{M-1} y^s_{M-1}
p_{0,0} \cdots p_{0,N-1}
\vdots
p_{K-1,0} \cdots p_{K-1,N-1}
限制条件已修订(日本标准时间 8 月 1 日 19:30)
- 废弃物种类数量 N 满足 5\leq N\leq 20.
- 分拣机安装位置数量 M 满足 10N\leq M\leq 50N.
- 分拣机类型数量 K 满足 N\leq K\leq 4N.
- 坐标 (x^d_i,y^d_i) 的 i-th 处理器安装位置是满足以下条件的整数 0\leq x^d_i,y^d_i\leq 10^4.
- 坐标 (x^s_i,y^s_i) 的 i第一个分拣机安装位置是满足以下条件的整数 0\leq x^s_i,y^s_i\leq 10^4.
- 入口坐标和所有安装位置都是相互不同的。
- 概率 p_{i,j} 那个分拣机 i 路线浪费类型 j 到 Exit 1 是一个实数,满足 0\leq p_{i,j}\leq 1.
输出
传送带的目的地由以下数字表示:
- 如果目的地是 i-第处理器安装位置: i
- 如果目的地是 i第分拣机安装位置: N+i
让 d_i (0\leq d_i\leq N-1)是安装在 i-第处理器安装位置。 让 s (0\leq s\leq N+M-1) 是代表传送带从废物入口到达的目的地的数字。 以指定格式将以下内容输出到标准输出:
d_0 \cdots d_{N-1}
s
然后输出 M 附加行。
的 i- 第行应根据状态输出 i第分拣机安装位置:
- 如果未安装分拣机:
-1
- 如果 k-th (0\leq k\leq K-1) 已安装分拣机,1号出口传送带的目的地为 v_1,从出口 2 开始是 v_2 (0\leq v_1,v_2\leq N+M-1):
k v_1 v_2
如果传送带的目的地是分拣机安装位置,则必须在那里安装分拣机。
示例解决方案 (Python)
1. 安装类型的处理器 i 在 i-第处理器安装位置
2. 将废物入口连接到最近的分选机安装位置
3. 在该位置安装分类器类型 0,将出口 1 连接到概率最高的废物类型的处理器,将出口 2 连接到概率最低的类型的处理器
import sys
import math
input = sys.stdin.readline
# Read input
N, M, K = map(int, input().split())
processor_positions = []
for _ in range(N):
x, y = map(int, input().split())
processor_positions.append((x, y))
sorter_positions = []
for _ in range(M):
x, y = map(int, input().split())
sorter_positions.append((x, y))
prob = []
for _ in range(K):
row = list(map(float, input().split()))
prob.append(row)
# Install processor of type i at position i
proc_assign = ' '.join(str(i) for i in range(N))
# Connect inlet (0,5000) to the nearest sorter installation location
inlet = (0, 5000)
dist_sq = [((x - inlet[0])**2 + (y - inlet[1])**2, i) for i, (x, y) in enumerate(sorter_positions)]
_, nearest_i = min(dist_sq)
inlet_conn = N + nearest_i
# Install sorter type 0, connect Exit 1 to processor with highest prob, Exit 2 to lowest
first_row = prob[0]
imax = first_row.index(max(first_row))
imin = first_row.index(min(first_row))
sorter_assigns = []
for i in range(M):
if i == nearest_i:
sorter_assigns.append(f"0 {imax} {imin}")
else:
sorter_assigns.append("-1")
print(proc_assign)
print(inlet_conn)
print("\n".join(sorter_assigns))
输入生成
- \mathrm{rand}(L,U): 统一生成一个整数 L 和 U,包括在内。
N, M,和 K 均在各自的范围内均匀随机生成。
的坐标 N 处理器安装位置和 M 分拣机安装位置是使用以下过程生成的,总共创建 N+M 坐标,其中第一个 N 用于处理器位置,其余的 M 用于分拣机位置。
将使用的坐标集初始化为 S=\{(0,5000)\}.
生成坐标 (x,y) 与 x=\mathrm{rand}(0,10^4), y=\mathrm{rand}(0,10^4).
如果在欧氏距离内没有点
生成点的 100 位于 S,接受该点并将其添加到 S.
重复此操作,直到
已生成 N+M 点。
每个分类概率 p_{i,j} 独立生成为 \mathrm{rand}(1000,9000)\times 10^{-4}.
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
样本输入 1
13 133 47 1858 8963 2368 1117 2507 4965 7710 890 1468 578 3244 9299 5025 8511 9642 4334 599 4476 1388 2454 4779 5389 8676 3397 6156 8034 4102 6415 8251 3509 9320 4268 1193 1486 4847 2021 4440 9046 8991 8142 6633 5942 3778 8637 6876 74 6067 1863 8407 3044 1604 822 9775 4772 9083 1045 9803 847 7455 5575 3183 1259 8407 2922 371 3058 4890 3331 4014 5211 2054 4998 4121 2752 6559 6840 5346 2079 5773 6895 335 4826 2920 8652 7735 1367 6162 8431 9157 7821 4653 704 6642 7613 8857 6949 3623 8476 7022 6237 4959 8592 2981 3756 2329 7006 2328 3175 249 3861 3051 8548 2673 996 714 7101 9170 2616 70 490 9474 7442 3173 4483 6962 8988 129 8154 1965 3249 9297 1953 6438 9318 5926 6158 1136 6845 2191 7256 475 5531 3383 5500 4499 7348 1062 6942 3835 7850 6357 1687 7532 3576 8723 8738 760 2627 8460 5002 4686 7214 9095 2003 5976 7913 3428 9235 266 2484 527 8521 6142 4813 588 1327 1267 4124 5523 7202 6286 4698 2459 6133 3068 689 5979 5443 3284 133 4996 3507 7965 9183 5634 316 4940 7810 1672 8535 6853 4148 9340 5193 8069 632 1836 7667 2546 2085 4054 4133 3953 2870 842 1426 3115 3095 3310 6422 2990 4161 9395 8903 5047 8714 5566 3742 6731 7534 6722 749 4764 7151 1713 7025 4254 6934 6297 8912 4215 462 3514 8224 398 9070 6611 8531 9596 5432 1411 5057 7552 8981 6596 3135 6479 5998 7299 423 2041 3637 710 6793 2958 189 1252 5867 3588 6591 1057 5697 8112 9569 6711 6792 6763 6384 616 7507 5311 7674 9751 5960 5991 4435 3668 4186 7865 9219 1535 4695 0.7947 0.5717 0.1458 0.7273 0.1395 0.5274 0.7105 0.6630 0.5254 0.1861 0.8898 0.4124 0.8373 0.8285 0.6842 0.7812 0.7602 0.8161 0.6065 0.2316 0.3189 0.1706 0.1754 0.5127 0.1849 0.1398 0.5147 0.6140 0.5256 0.7881 0.4148 0.3610 0.7228 0.5083 0.7442 0.6778 0.7014 0.1979 0.7725 0.3479 0.5942 0.2791 0.6912 0.5923 0.7850 0.8101 0.4307 0.1955 0.8941 0.5841 0.7685 0.3365 0.4116 0.3389 0.7719 0.8792 0.5796 0.5751 0.1132 0.2053 0.5233 0.8496 0.5604 0.7999 0.8949 0.6201 0.3431 0.3317 0.8918 0.7173 0.8363 0.8314 0.7755 0.2087 0.1003 0.3819 0.8538 0.1853 0.5341 0.2075 0.3356 0.1762 0.2904 0.8025 0.5798 0.8951 0.5324 0.6448 0.3785 0.5311 0.8397 0.7767 0.4043 0.7621 0.4336 0.7617 0.3717 0.5117 0.8811 0.3867 0.5574 0.2229 0.4948 0.2109 0.2918 0.1748 0.6747 0.8715 0.2433 0.5604 0.8109 0.6585 0.4850 0.4937 0.7828 0.5056 0.4923 0.2074 0.5636 0.2931 0.7722 0.4598 0.3112 0.2513 0.1173 0.8946 0.2885 0.3746 0.4158 0.1289 0.6646 0.8395 0.1890 0.5334 0.1160 0.7439 0.5963 0.1967 0.3549 0.2631 0.4714 0.3812 0.1210 0.5868 0.4050 0.2678 0.2920 0.6503 0.3704 0.4336 0.5353 0.6986 0.1129 0.2086 0.1183 0.2040 0.4108 0.1430 0.2123 0.4538 0.6206 0.2628 0.1833 0.6750 0.7179 0.4557 0.5837 0.3481 0.8241 0.7121 0.6299 0.6964 0.6125 0.7442 0.4419 0.2720 0.1329 0.2044 0.6554 0.2180 0.7193 0.7337 0.7011 0.1872 0.6595 0.1431 0.4645 0.5205 0.7408 0.1855 0.8220 0.7275 0.2853 0.3204 0.4627 0.5218 0.6348 0.3389 0.8584 0.2942 0.2740 0.4592 0.2506 0.8733 0.8386 0.6548 0.2667 0.8584 0.8958 0.7544 0.4056 0.1245 0.6517 0.8921 0.7763 0.3818 0.7530 0.3751 0.6342 0.7434 0.4215 0.2749 0.3961 0.4172 0.1673 0.4351 0.3963 0.5220 0.2972 0.3792 0.5992 0.7891 0.5944 0.4958 0.5049 0.1172 0.6678 0.4131 0.2468 0.7376 0.6962 0.5892 0.3075 0.4466 0.6821 0.3681 0.3261 0.2087 0.1496 0.2146 0.6869 0.4596 0.7237 0.2283 0.2242 0.7294 0.1675 0.8079 0.6417 0.7165 0.4842 0.3767 0.7664 0.7524 0.5782 0.1098 0.3663 0.5658 0.3647 0.1522 0.6769 0.7871 0.5725 0.4457 0.2750 0.3091 0.7717 0.6955 0.1686 0.5195 0.5703 0.7169 0.4944 0.5972 0.2510 0.3722 0.6483 0.3851 0.3562 0.8226 0.4714 0.5673 0.2170 0.8736 0.8041 0.4816 0.6178 0.1427 0.1894 0.1430 0.2933 0.3126 0.8151 0.7037 0.5676 0.2704 0.3305 0.6220 0.1465 0.2080 0.5824 0.1398 0.2149 0.2998 0.1146 0.8847 0.8714 0.1295 0.8328 0.4172 0.1081 0.3282 0.3044 0.7896 0.5094 0.5783 0.8544 0.7956 0.2967 0.7709 0.1041 0.1021 0.6928 0.5704 0.2814 0.5847 0.5448 0.6967 0.3834 0.5092 0.8551 0.7886 0.1314 0.3960 0.6900 0.4573 0.5070 0.6776 0.6555 0.5269 0.3392 0.1611 0.5018 0.1274 0.1432 0.3938 0.4762 0.5130 0.8322 0.8457 0.8087 0.1703 0.1075 0.1604 0.1997 0.7419 0.1717 0.4030 0.4894 0.3377 0.3162 0.6859 0.1615 0.8698 0.5788 0.8138 0.5818 0.4859 0.3316 0.8085 0.4157 0.8243 0.4599 0.5926 0.5802 0.6918 0.1755 0.3048 0.5425 0.3713 0.5403 0.1570 0.4645 0.7979 0.2681 0.8216 0.2177 0.5360 0.6601 0.7411 0.4305 0.8996 0.8515 0.3653 0.8646 0.2023 0.2481 0.5197 0.8658 0.8288 0.2090 0.3178 0.3384 0.6897 0.4686 0.1087 0.2876 0.4619 0.5801 0.5664 0.6368 0.6487 0.8110 0.6732 0.1831 0.4944 0.6158 0.5406 0.5401 0.4234 0.3891 0.2370 0.7762 0.8843 0.8458 0.6728 0.3381 0.4985 0.2366 0.8303 0.1040 0.5701 0.1297 0.3075 0.6430 0.4957 0.7719 0.6939 0.7531 0.5474 0.5737 0.7540 0.4508 0.1765 0.7806 0.5881 0.7300 0.7944 0.7544 0.1365 0.1780 0.5800 0.5754 0.3439 0.8311 0.4328 0.7358 0.3163 0.2535 0.5585 0.6483 0.1642 0.1291 0.8911 0.7827 0.8863 0.7378 0.4760 0.3481 0.8681 0.7335 0.4697 0.1786 0.3000 0.4476 0.3325 0.7877 0.5377 0.6881 0.5053 0.8013 0.5359 0.6286 0.3323 0.8809 0.5817 0.2729 0.3885 0.2775 0.4435 0.8356 0.2798 0.5751 0.6667 0.4997 0.7838 0.6363 0.6267 0.7182 0.6751 0.7085 0.4753 0.7842 0.8322 0.4385 0.7766 0.1075 0.1791 0.8696 0.1037 0.4336 0.8460 0.5259 0.5350 0.7094 0.1762 0.4207 0.7375 0.4378 0.2340 0.5642 0.7896 0.3129 0.1505 0.5580 0.3774 0.7196 0.7524 0.8902 0.4146 0.1722 0.7837 0.3907 0.2465 0.3367 0.6686 0.7948 0.1337 0.8616 0.4249 0.3155 0.2698 0.1273 0.4942 0.7133 0.2159 0.7039 0.7372 0.4182 0.5986 0.3626 0.1562 0.1946 0.5486 0.1648 0.2525 0.7382 0.8283 0.3628 0.4541 0.2651 0.8978 0.1668 0.4790 0.3921 0.7325 0.3574 0.4265 0.8023 0.8647 0.8215 0.4398 0.2749 0.2215 0.8907 0.4803 0.6133 0.1684 0.1372 0.6250 0.3488 0.5522 0.1836 0.2820 0.2808 0.1747 0.1864 0.7046 0.4214 0.6384 0.4454 0.7190 0.2064 0.4953 0.3946 0.7983 0.7207 0.3334 0.5841 0.6460 0.2462
示例输出 1
0 1 2 3 4 5 6 7 8 9 10 11 12 40 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 10 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1