Problem 3E: K8s - Easy Version

Problem 3E: K8s - Easy Version

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 3E: K8s - Easy Version

时间限制:2000ms

空间限制:512MB

题目描述

电自院最近新设立了一台AI推理服务器,旨在预测校内各楼宇的耗电量。尽管这台AI服务器上装有多张显卡,但是由于负责该项目的同学,小F,并不会任何的后端技术,导致现在这台服务器只能串行处理请求,无法利用这么多显卡。由于小F的导师对这台服务器的QPS如此之低感到不满,一些改进方案被提了出来:

AI服务器上现有\(n\)个显卡,依次编号为\(0,1,2,...,n-1\),编号为\(i\)的显卡算力为\(c_i\)。为充分利用这些显卡,小F为每个显卡都创建了一个Pod,每个Pod中都运行着调用某块显卡进行AI推理的程序。由于每个Pod中的显卡型号可能有差别,且任务的种类繁多,因此不同任务在不同Pod中的运行时间会有差异。经过研究统计,小F发现,AI服务器会收到\(m\)种推理任务,编号为\(0,1,2,...,m-1\),类型编号为\(i\)的任务的规模为\(a_i\)。当类型编号为\(i\)的任务在编号为\(j\)的显卡上运行时,所需要的时间为\([a_i/c_j]\)毫秒。这里符号\([x]\)表示不大于\(x\)的最大整数。

为了合理的将推理任务分配给Pod,小F设计了一种分配机制。每当AI服务器收到一个推理任务时,就会把这个任务分配给**响应用时最短**的Pod;如果有多个Pod的响应用时均最短,那么分配给**完成任务的数量(含正在运行的任务)最少**的Pod;如果有多个Pod的响应用时均最短且完成任务数量一致,那么分配给**编号最小**的那个Pod。

某时刻一个任务在某个Pod上的“响应用时”的定义为:将这一任务加入该Pod后,该Pod**开始**这一任务的时刻与当前时刻的时间差。例如,一个Pod正在运行一个需要10毫秒的任务,当前该任务已经运行了5毫秒,而且恰好还有3个用时分别为12毫秒、31毫秒和8毫秒的任务等待在该Pod上运行,如果有一个此时有一个新任务可能会分配到该Pod上,那么当前时刻这个新任务在该Pod上的响应时间就是\((10-5)+(12+31+8)=56\)毫秒。

现在,AI服务器收到了\(q\)个推理任务,第\(i\)个推理任务的到达服务器的时刻为\(t_i\)毫秒,类型编号为\(k_i\)。这里保证所有\(t_i\)严格递增,即对于\(\forall i\in\{1,2,...,q-1\}, t_i< t_{i+1}\)。小F希望知道,按照上述方案,这些推理任务都会被分配给哪个Pod。

由于小F的代码水平稀烂,因此他无法完成这项工作。因此,他现在求助于你,希望你能帮他完成这个程序。

输入格式

第1行,包含3个整数\(n,m,q\);

第2行,包含\(n\)个整数,分别表示\(c_0,c_1,c_2,...,c_{n-1}\);

第3行,包含\(m\)个整数,分别表示\(a_0,a_1,a_2,...,a_{m-1}\);

第4~\((q+3)\)行,每行2个整数,第\((3+i)\)行的整数分别表示\(t_i,k_i\),

一行内的多个整数之间使用1个空格分开,且每行的开头和末尾没有多余空格。

输出格式

输出\(q\)行,每行1个整数。第\(i\)行的整数表示服务器接收到的\(i\)个推理任务被分配到的Pod的显卡编号。

样例输入

2 3 5
6 8
190 328 112
0 1
12 0
38 0
39 2
204 1

样例输出

0
1
1
0
0

样例解释

本例中有2种显卡和3种任务。

时间/ms 任务类型编号 显卡0任务数 显卡0的等待队列 显卡0的响应时间/ms 显卡1任务数 显卡1的等待队列 显卡1的响应时间/ms 选择哪个显卡?
0 1 0 0 0 0 0号显卡
12 0 1 [54ms],首个任务已运行12ms 54-12=42 0 0 1号显卡
38 0 1 [54ms],首个任务已运行38ms 54-38=16 1 0 1号显卡
39 2 1 [54ms],首个任务已运行39ms 54-39=15 2 [23ms],首个任务已运行1ms 22 0号显卡
204 1 1 0 2 0 0号显卡

数据范围及约定

对于\(20\%\)的数据,满足\(n,q \le 100, m\le 10\)

对于\(60\%\)的数据,满足\(n,m,q \le 1000\);

对于\(100\%\)的数据,\(1 \le n,q \le 2\times 10^5\),\(1\le m \le 1000\),\(0\le t_i\le 10^9\),\(0 \le k_i < m\),\(1\le c_i,a_i\le 10^9\),所有输入数值均为非负整数。

提示

猜猜这题为什么叫K8s?

2024春 悬赏令第三周

未参加
状态
已结束
规则
OI
题目
6
开始于
2024-04-28 18:30
结束于
2024-05-05 08:00
持续时间
157.5 小时
主持人
参赛人数
44