2026年第38届国际信息学奥林匹克竞赛（IOI ）第一试赛题试卷

UZBEKISTAN ballmachine Day 1 Tasks IOI 2026 TASHKENT Chinese(CHN) 弹球机 Madina发明了一台弹球机，以供参加IOI的人们娱乐。机器的内部构造是这样的： ·机器有N个结点，编号为从0到N一1。结点N一1被称作根。 ·对每个结点u(0≤u<N-1),其父结点为满足P{u>u的某个结点P心，而结点u则是 P心的子结点。根结点没有父结点。没有子结点的结点被称为叶结点。 你不知道N以及各个结点u的父结点Pu。不过，Madina会告诉你叶结点的数量M,而这些叶结点 的编号为0,1，·，M一1。你的任务是，通过操作机器来确定它的内部构造。 机器的每个结点上最多可以放一个球，而且每个球都有一个非负整数值。如果某个结点上有值为心的球， 我们就说这个结点的值为x。某个结点上如果放了一个球，就称为是被占的；否则，它就是空的。在最开 始时，所有结点都是空的。 你可以做如下两种操作： ·insert(U,X):尝试把值为X的一个新球放到叶结点U处。 。如果叶结点U是被占的，该操作将返回false并且不会放上这个球。 。如果叶结点U是空的，这个球将会放到结点U上。接下来，这个球会不断地从当前所在结 点移向它的父结点，前提是父结点是空的。当遇到根结点或者某个结点的父结点已经被占， 移动就会停止。该操作将返回true。 ·collect(0:如果根结点是空的（这意味着机器是空的），collect将返回一个空数组。否则，下面 所给出的递归函数traverse将收集当前机器中所有球的值，并且放进数组S。最初数组S是空 的，并且以调用traverse(N~1)开始。 traverse(u): 将结点u上的球的值追加到S的末尾 令c[u]为u的被占子结点的列表 根据c[u]上球的值，对c[u]进行非降排序（如果有多个结点的值相同， 它们可能会以任意顺序出现) 对于c[u]中的每个v: traverse(v) 在该函数结束后，所有球都将被移出该机器，而co1Lect则返回S。 ballmachine(1 of 6) 例如，设想有某台机器，它有N=7个结点，对应的父结点的数组为P=[4,6,5,5,6,6]。左图给出了 标有结点编号的空机器，而右图则给出了在某个insert操作序列（该序列将在例子一节中给出）完成后 的可能状态。 6 5 20 10 20 在collect()被调用时，根结点（结点6）是被占的，所以S被初始化成S=],而traverse(6) 将被调用。 traverse(6):结点6的值为0；将其追加到S并得到S=[0。结点6的子结点是4,1和5，而且 全部都是被占的。它们的值分别是20,10和20。非降排序得到c6]=1,5,4(注意，c6]=[1,4,5] 也是对的，因为结点4和5有相同的值)。该函数将根据这个排序，对c6]中的每个结点调用 traverse。 ·traverse(1):结点1的值为10；将其追加到S将得到S=[0,10]。结点1没有被占的子结 点，因此该调用结束。 ·traverse(5):结点5的值为20；将其追加到S将得到S=0,10,20]。结点5有一个被占的 子结点2，因此c5]=[2而该函数将调用traverse(2)。 。traverse(2):结点2的值为30；将其追加到S将得到S=[0,10,20,30]。结点2没有 被占的子结点，因此该调用结束。 。当前执行将返回到traverse(5),而它已经处理了c[5]中的全部子结点，因此该调用结 束。 ·traverse(4):结点4的值为20；将其追加到S将得到S=[0,10,20,30,20]。结点4没有被 占的子结点，所以该调用结束。 所有的调用结束，而且没有剩余结点需要处理。最终，所有球将被从机器中移出，而collect将返回数 组S=[0,10,20,30,20]。 你的任务是确定结点数量N,并且给出能够刻画机器构造的父结点数组 R=[R0],1,·,RN-2,不过那些中间结点（既非叶结点也非根结点）的编号方案可以有所不 同。形式化地来说，对于某个所给出的数组R,如果能够对机器中的各个结点u赋以不同的编号[u (0≤Lu<N)且满足如下条件，则R被认为是正确的： ballmachine(2 of 6) ·对所有0≤u<M以及u=N-1,都有Lu=u,并且 ·对所有0≤u<N-1都有L[Pu=R[Lu。 这里不要求u>u。在给出你的答案时，机器必须是空的： 令K为collect的操作次数，而B为全部insert调用中所有球的最大值。令C=K+B。这里 C必须不超过1000。你在某些子任务上的得分取决于C的值。 实现细节 你需要实现以下函数。 std:vector<int>find structure(int M) 。M:机器中的叶结点数量。 ·在每个测试用例上，该函数将被调用恰好一次。 ·该函数必须返回一个长度为N-1的数组R=[R0,R[1,.·,R[N一2，该数组应该正确地给 出父结点。 为了和机器交互，你的函数可以调用下面的两个函数。 第一个函数是： bool insert(int U,int X) ·U:希望放上球的叶结点的编号。必须满足0≤U<M。 ·X:球的整数值。必须满足0≤X≤1000。 ·如果球可以成功放入，该函数返回true,而如果叶结点U是被占的，则返回false。 ·该函数最多可以被调用500000次。 第二个函数是： std:vector<int>collect() ·收集所有被放人的球的值，清空机器，并且返回所收集到的数组S。 在你的程序执行的任何时刻，如果C的值超过1000，你的解答将会收到判定结果0 utput isn't correct:Too many resources used. 在调用find_structure之前，机器的构造即已确定。评测程序是确定性的，其含义是，如果你运行它 两次，并且两次都做相同的操作序列，对co1Lect的调用将返回相同的数组。 ballmachine (3 of 6) 约束条件 ·2≤N≤1000 ·1≤M≤200 ·M<N 子任务 子任务 分数 额外的约束条件 1 5 根结点恰好有M个子结点。 2 10 M≤3 3 25 N≤200，M≤45 4 60 没有额外的约束条件。 在子任务3和4中，你的得分取决于C的值，规则如下。 子任务3(25分) 限制 得分 1000<C 0 45<C≤1000 13 C≤45 25 子任务4(60分) 限制 得分 1000<C 0 200<C≤1000 7 71<C≤200 47-号 44<C≤71 104-C C≤44 60 例子 考虑在题面描述中的同一台机器，也就是N=7,M=4以及P=[4,6,5,5,6,6]。这台机器将再次在 下图中给出： ballmachine(4 of 6) 6 评测程序将做如下调用： find structure(4) 该函数可以做如下序列调用： 1.insert(0,):叶结点0是空的，所以值为0的球被放到叶结点0处。结点P0]=4是空 的，因此球会移动到结点4。结点P4=6是空的，因此球会移动到结点6。由于结点6是根结 点，移动停止。本调用返回true。 2.insert(3,20):叶结点3是空的，所以值为20的球被放到结点3处。结点P3]=5是空 的，因此球会移动到结点5。由于P5)=6已经被占，移动停止。本调用返回true。 3.insert(1,10):叶结点1是空的，所以值为10的球被放到叶结点1处。由于P[1]=6已经 被占，球会停在结点1处。本调用返回true。 4.insert(2,30):叶结点2是空的，所以值为30的球被放到叶结点2处。由于P[2=5已经 被占，球会停在结点2处。本调用返回true。 5.insert(1,25):叶结点1已经被占，所以球不能被放到叶结点1处。本调用返回false。 6.insert(0,20):叶结点0是空的，所以值为20的球被放到叶结点0处。结点P0]=4是空 的，所以球移动到结点4处。由于P[4=6已经被占，移动停止。本调用返回true。 最终所得到的球的状态，已经在题面描述中给出。 接下来，函数将调用： collect() 该调用的执行方式已经在题面描述中解释过了，因此该调用会返回S=0,10,20,30,20]。此后，机器将 被清空。 接下来，函数可以调用insert(2,25)。叶结点2是空的，所以值为25的球被放到叶结点2处。这个 球移动到结点5处，然后到结点6处，然后就此停住。调用返回true。最终所得到的球的状态，将在下 图中给出。 ballmachine (5 of 6) 25 最后，函数可以调用collect(),它会返回S=[25]并且清空机器。 在这里，find structure可以返回的正确的父结点数组有两种：R=P=[4,6,5,5,6,6](对应于标 签L=0,1,2,3,4,5,6),以及R=[5,6,4,4,6,61(对应于标签L=[0,1,2,3,5,4,6])。在这个例 子中，K=2且B=30,因此C=32。 评测程序示例 输入格式： NM P[0]P[1]P[2]..P[N-2] 输出格式： KBC 0 R[o]R[1]R[2]..R[Q-1] 在这里，Q为find_structure所返回的数组R的长度。 ballmachine (6 of 6) UZBEKISTAN monuments Day 1 Tasks IOI 2026 TASHKENT Chinese(CHN) 纪念碑 撒马尔罕著名的雷吉斯坦广场内有N座纪念碑，它们排列成一条穿过广场中心的直线。这些纪念碑的编 号从0到N一1。编号为i(0≤i<N)的纪念碑初始位于整数坐标X[处，广场中心位于坐标0。 建筑师要求建筑布局关于中心完美对称。他们希望通过移动其中一些（数量可能为零）纪念碑，使得最终 的建筑布局关于坐标0对称，可以形式化描述如下： ·所有纪念碑必须位于整数坐标处。 ·每个整数坐标可以放置零个、一个或多个纪念碑。 ·对于任意整数x>0,位于坐标x处的纪念碑数量必须等于位于坐标一x处的纪念碑数量。坐标0 上可以放置任意数量的纪念碑（数量可能为零）。 然而，有M座古老纪念碑年久失修导致无法移动。它们的编号为P0,P[1],·,P[M一1]。这M座 纪念碑必须停留在其原始坐标上，其余N一M座纪念碑可以移动到任意整数坐标处。在移动过程中，纪 念碑之间互不干扰。 将一座纪念碑从坐标α移动至坐标b的代价为a一b。总代价定义为所有被移动纪念碑的代价之和。 你的任务是求出使所有纪念碑的建筑布局关于坐标0对称的最小总代价；如果无法在给定约束下实现对 称，则判定为无解。 实现细节 你要实现以下函数： Long long get_cost(std:vector X,std:vector P) 。·X:长度为N的非递减数组，给出纪念碑的初始坐标。 ·P:长度为M的严格递增数组，给出古老纪念碑的编号。 ·对于每个测试用例，该函数恰好被调用一次。 该函数应返回一个整数：使建筑布局对称的最小总代价；如果不可能，则返回一1。 约束条件 ·1≤W≤500000 ·0≤M≤N monuments(1 of 4) ·-10°≤X0≤X[1≤..≤X[N-1≤109 ·0≤P0<PI<..<PM-1<N 子任务 子任务 分数 额外的约束条件 1 3 M=N 4 M=0 3 对于所有满足0≤j<M的j,均有X[P<0。 4 6 N≤10 5 5 N≤19 6 5 N≤32 7 13 N≤200 8 17 N≤4000 13 M≤4000 10 29 没有额外的约束条件。 例子 例1 考虑以下调用： get_cost([-3,-2,1,3],[1,21) 纪念碑的初始建筑布局如下图所示。 -3 -2-10 1 23 共有N=4座纪念碑，初始坐标分别为〔-3，-2,1,3]。古老纪念碑的编号为P0]=1和P[1]=2。即 坐标为X[P[0]=一2和X[P[1刃=1的纪念碑不能移动。其余坐标为-3和3的纪念碑可以移动。 monuments(2 of 4) 为使总代价最小且达到对称，我们需要如下移动纪念碑： 。将坐标为-3的纪念碑移至-1，代价为（一3）一（-1)儿=2。 。将坐标为3的纪念碑移至2，代价为3一2=1。 移动后布局变为对称。 -3 -2 -1 2 3 总移动代价为2+1=3，因此该函数应返回3。 例2 考虑以下调用： get_cost([2,2,2,3],[1) 此处M=0,表示没有古老纪念碑，所有纪念碑均可移动。 一种最小总代价的解法是将所有纪念碑移至坐标0。每座纪念碑的移动代价为： ·纪念碑0、1和2的代价为2-0=2。 ·纪念碑3的代价为3-0=3。 总代价为2十2十2十3=9。因此该函数应返回9。注意，存在其他总代价相同的解法。 例3 考虑以下调用： get_cost([1,2,3,4],[0,1,2,3]) 全部4座纪念碑均为古老纪念碑，无法移动。 由于它们的坐标均为正数，无法使建筑布局关于0对称。 因此该函数应返回-1。 monuments(3 of 4) 评测程序示例 输入格式： NM X[0]X[1]..X[N-1] P[0]P[1]..P[M-1] 注意，如果M=0,则第三行可能为空行。 输出格式： 其中，C为get_cost的返回值。 monuments (4 of 4) UZBEKISTAN tiling IOI 2026 TASHKENT Day 1 Tasks Chinese(CHN) 方块游戏 Barchin和Charos正在一个由2N×2M正方形单元格组成的网格上玩游戏。从上到下，行的编号依次 为0到2N-1;从左到右，列的编号依次为0到2M-1。对于0≤i<2N和0≤j<2M,我 们将i行和第了列的单元格表示为(i,)。 Barchin依次给Charos N·M个方块。每个方块都是一个2×2的正方形，由四个1×1小方块组成。 Barchin已经将方块中的每个小方块涂成黑色或白色，并且保证至少有一个小方块是白色的。 在不知道之后会收到哪些方块的情况下，Charos必须在收到每个方块后立即将其放置在网格上。方块不 能旋转。每个方块必须完全放置在网格内，且正好覆盖四个网格单元格。此外，每个方块左上角的小方块 必须覆盖一个行坐标和列坐标均为偶数的单元格。网格中的每个单元格最多只能被一个方块覆盖。 如果在某次放置一个方块后，存在一个2×2的正方形，其中四个单元格被四个黑色小方块覆盖，则 Barchin获胜。形式上，如果单元格(a,b)、(a+1,b)、(a,b+1)、(a+1,b+1)都被黑色小方块覆 盖（其中0≤a<2N-1且0≤b<2M-1),则Barchin获胜。其中a和b不必是偶数。 如果Charos放置了所有N·M个方块，而Barchin始终未获胜，则Charos获胜。注意，放置N·M 个方块将完全覆盖网格。 你的任务是为Charos制定赢得游戏的策略。可以证明，在给定约束下，无论之后收到的方块如何着色， Charos总能通过正确放置方块以保证获胜。 实现细节 你要实现以下两个函数： void init(int N,int M) ·N：网格中行数的一半。 。M:网格中列数的一半。 ·该函数在每个测试用例中只调用一次，即在你的程序执行开始时调用。 std:pair<int,int>receive block(int TL,int TR,int BL,int BR) ·T工、TR、BL、BR:分别为当前方块左上角、右上角、左下角和右下角小方块的颜色，如 下图所示。每个值要么是0（白色)，要么是1（黑色）。 tiling (1 of 4) ·在首次调用init之后，每个测试用例将调用此函数恰好N·M次。 TL TR BL BR 此函数应返回一对整数（乞，），其中i是该方块左上角小方块应放置的单元格的行坐标，了是该单元格的 列坐标。元和了都必须是偶数，并且该方块覆盖的2×2区域不得与任何先前放置的方块重叠。 如果receive_block返回的整数对不满足这些要求，或者放置方块后，一个2×2正方形单元格完全被 黑色小方块覆盖，评测程序将立即终止你的程序，并且该测试用例的判定结果为Output isn't correct。 评测程序的行为不具备自适应性。这意味着在调用init之前，Barchin交给Charos的方块顺序就已经固 定了。 约束条件 对于每个方块，令S为其包含的四个小方块中黑色小方块的数量。即S=TL+TR+BL十BR。 ·1≤N,M≤100 ·对于每个方块，0≤S≤3。 子任务 子任 分 务 数 额外的约束条件 1 6 每个方块的S=1,且N=2。 每个方块的S=3。N=M,N为偶数，且四种可能的方块着色方案每一种都恰 2 16 好出现平次。 3 10 每个方块的S=1。 4 29 每个方块的S≤2。 5 39 没有额外的约束条件。 例子 考虑一次游戏，其中N=1,M=2,因此网格有2行和4列。评测程序首先调用 tiling (2 of 4) init(1,2) 初始状态下，所有单元格均为空。网格如下所示： 123 需要放置N·M=2个方块。假设Barchin给出一个方块，其中包含三个黑色小方块和一个位于右上角 的白色小方块。评测程序调用： receive block(1,0,1,1) Charos决定将此方块放置在网格的左侧，返回(O,O)。 现在的网格看起来是这样的： 0123 Barchin随后给出另一个方块，其左上角为白色，其余三个小方块为黑色： receive block(0,1,1,1) 在剩余的网格单元格中，唯一行和列均为偶数且能作为2×2方块左上角的单元格是(0,2)，因此 Charos返回(0,2)。最终的网格如下所示： tiling (3 of 4) 0123 因为没有2×2方格被黑色小方块完全覆盖，所以Charos成功放置了所有方块，Barchin始终未获胜。 Charos赢得游戏。 评测程序示例 输入格式： NM TL[O]TR[O]BL[O]BR[O] TL[1]TR[1]BL[1]BR[1] TL[NM-1]TR[NM-1]BL[NM-1]BR[NM-1] 输出格式： R[0]C[0] R[1]C[1] R[NM-1]C[NM-1] 这里，R[]和C[]是第k次调用receive_block返回的一对整数。 tiling (4 of 4) UZBEKISTAN ballmachine Day1Tasks IOI 2026 TASHKENT English(ISC) Ball Machine Madina has invented a ball machine to entertain the participants of the IOI.The internal structure of the machine is as follows: The machine consists of N nodes,indexed from 0 to N-1.Node N-1 is called the root. For each node u with 0<u<N-1,the parent of node u is a node Plu]with Plu>u, and node u is a child of Plu.The root has no parent.A node with no children is called a leaf. You do not know N or the parent Plu]of any node u.Instead,Madina tells you M,the number of leaves,and that the indices of the leaves are 0,1,...,M-1.Your task is to determine the internal structure of the machine by operating it. Each node of the machine can hold at most one ball,and each ball has a value which is a non- negative integer.We say that a node has value x if it holds a ball with value x.A node is occupied if it contains a ball;otherwise,it is free.Initially,every node is free. You can perform two kinds of operations: insert(U,X):attempt to insert a new ball with value X at leaf U. o If leaf U is occupied,the operation returns false without inserting the ball. o If leaf U is free,the ball is placed at node U.Then the ball repeatedly moves to the parent of its current node as long as that parent is free.The movement stops when the ball reaches the root or a node whose parent is occupied.The operation returns true. collect():if the root is free(which means the machine is empty),collect returns an empty array.Otherwise,the recursive procedure traverse described below gathers the values of all balls that are currently in the machine into an array S.Initially,the array S is empty and traverse(N 1)is called. traverse(u): append the value of the ball at node u to the end of s let c[u]be the list of the occupied children of u sort c[u]in non-decreasing order according to the values of the balls at those nodes (if multiple nodes have the same value,they can appear in any order) for each v in c[u]: traverse(v) ballmachine(1 of 7) After this procedure completes,all balls are removed from the machine,and collect returns S. For example,consider a machine with N=7 nodes and parent array P=[4,6,5,5,6,6].The picture on the left displays the empty machine with node indices,while the picture on the right shows a possible configuration of balls after some sequence of insert operations(this sequence is given in the Example section). 6 0 5 20 10 20 When collect (is called,the root (node 6)is occupied,so S is initialized as S=[]and traverse(6)is called. traverse(6):node 6 has value 0;appending it to S gives S=[0].The children of node 6 are 4,1, and 5,all of which are occupied.Their values are 20,10,and 20,respectively.Sorting in non- decreasing order yields c[6]=[1,5,4](note that c6]=[1,4,5]would also be valid,since nodes 4 and 5 have the same value).The procedure then calls traverse on each node in c6]in that order. traverse(1):node 1 has value 10;appending it to S gives S=0,10.Node 1 has no occupied children,so this call ends. traverse(5):node 5 has value 20;appending it to S gives S=0,10,20.Node 5 has one occupied child,node 2,so c5][2]and the procedure calls traverse(2). o traverse(2):node 2 has value 30;appending it to S gives S=[0,10,20,30].Node 2 has no occupied children,so this call ends. o The execution returns to traverse(5)which has processed all children in c5,so its call ends. traverse(4):node 4 has value 20;appending it to S gives S=[0,10,20,30,20].Node 4 has no occupied children,so this call ends. All calls have completed and there are no more nodes to process.Finally,every ball is removed from the machine and collect returns the array S =[0,10,20,30,20]. ballmachine(2 of 7) Your task is to determine the number of nodes N and report an array of parents R=[RO],R1],...,RN-2]]that describes the structure of the machine,but with a potentially different labeling of the nodes that are not leaves and not the root.Formally,a reported array R is considered correct if it is possible to assign a distinct label Lu with 0<Lu<N to each node u of the machine such that: ·Lul=u for all0≤u<M and u=N-l,and ·L[Pull=R[L u]]for all0≤u<N-1. It is not required that Ru>u.The machine must be empty when you report your solution. Let K be the number of collect operations performed,and B be the maximum value of any ball across all insert calls.Let C=K+B.Then C must not exceed 1000.Your score in some subtasks depends on the value of C. Implementation Details You should implement the following procedure. std:vector<int>find structure(int M) M:the number of leaves in the machine. The procedure is called exactly once for each test case. The procedure must return an arrayR=[R,R1,...,RN-2]]of length N-1,a correct array of parents. To interact with the machine,your procedure can call the following two procedures. The first procedure is: bool insert(int U,int X) U:the index of the leaf where the ball should be inserted.The condition 0<U<M must be met. ·X:the integer value of the ball..The condition0≤X≤l000 must be met.. This procedure returns true if the ball was successfully inserted,or false if leaf U was already occupied. This procedure can be called at most 500 000 times. The second procedure is: std::vector<int>collect() ballmachine (3 of 7) Collects the values on all inserted balls,empties the machine,and returns the collected array S. If at any point during the execution of your program the value of C exceeds 1000,your solution will receive the verdict output isn't correct:Too many resources used. The structure of the machine is fixed before find structure is called.The grader is deterministic in the sense that if you run it twice and both runs perform the same sequence of operations,the calls to collect will return the same arrays. Constraints ·2≤N≤1000 ·1≤M≤200 ·M<N Subtasks Subtask Score Additional Constraints 1 5 The root has exactly M children. 2 10 M≤3 3 25 N≤200，M≤45 4 60 No additional constraints. In subtasks 3 and 4,your score depends on the value of C as follows. Subtask 3(25 points) Limits Score 1000<C 0 45<C≤100013 C≤45 25 ballmachine(4 of 7) Subtask 4(60 points) Limits Score 1000< 0 200<C≤1000 7 71<C≤200 47-号 44<C≤71 104-C C≤44 60 Example Consider the same machine as in the task description,so N =7,M=4,and P=[4,6,5,5,6,6]. The machine is again shown in the following figure: 4 0 The grader makes the following call: find structure(4) The procedure can make the following sequence of calls: 1.insert (o,0):leaf 0 is free,so a ball with value 0 is placed at leaf 0.Node P[o]=4 is free, so the ball moves to node 4.Node P[4]=6 is free,so the ball moves to node 6.Since node 6 is the root,the movement stops.The call returns true. 2.insert (3,20):leaf 3 is free,so a ball with value 20 is placed at leaf 3.Node P[3]=5 is free,so the ball moves to node 5.Since P5]=6 is occupied,the movement stops.The call returns true. 3.insert(1,10):leaf 1 is free,so a ball with value 10 is placed at leaf 1.Since P[1]=6 is occupied,the ball stays at node 1.The call returns true. 4.insert(2,30):leaf 2 is free,so a ball with value 30 is placed at leaf 2.Since P2]=5 is occupied,the ball stays at node 2.The call returns true. ballmachine(5 of 7) 5.insert(1,25):leaf 1 is occupied,so the ball is not placed at leaf 1.The call return false. 6.insert (0,20):leaf 0 is free,so a ball with value 20 is placed at leaf 0.Node P[o]=4 is free,so the ball moves to node 4.Since P[4]=6 is occupied,the movement stops.The call returns true. The resulting configuration of balls was already displayed in the task description. Next,the procedure can call: collect() The execution of this call was already explained in the task description,so this call returns S=[0,10,20,30,20].Afterwards,the machine is once again empty. Next,the procedure can call insert(2,25).Leaf 2 is free,so a ball with value 25 is placed at leaf 2.This ball then moves to node 5,and then to node 6,where it stops.The call returns true.The resulting configuration of balls is shown in the following figure. 5 Finally,the procedure can call collect()which returns S=[25]and empties the machine. There are two correct parent arrays that find_structure can return:R=P=[4,6,5,5,6,6] (which corresponds to the labeling=0,1,2,3,4,5,6]),andR=5,6,4,4,6,6](which corresponds to the labeling L=[0,1,2,3,5,4,6).In this example,K =2 and B=30,so C=32. Sample Grader Input format: NM P[0]P[1]P[2]...P[N-2] ballmachine (6 of 7) Output format: KBC Q R[0]R[1]R[2].·R[Q-1] Here,Q is the length of the array Rreturned by find structure. ballmachine(7 of 7) UZBEKISTAN monuments Day 1 Tasks IOI 2026 TASHKENT English(ISC) Monuments The famous Registan Square in Samarkand contains N monuments standing in a line that passes through the center of the square.The monuments are indexed from 0 to N-1.Monument i(for 0<i<N)is initially located at integer coordinate Xi].The center of the square is at coordinate 0. The architects require perfect symmetry with respect to the center.They want to move some (possibly zero)of the monuments so that the final configuration is symmetric about the coordinate 0.Formally: Every monument must be placed at integer coordinates. Each integer coordinate may contain zero,one,or multiple monuments. For every integer >0,the number of monuments at coordinate a must be equal to the number of monuments at coordinate-2.Any number of monuments(possibly zero)can be located at coordinate 0. However,M monuments are ancient and too fragile to be moved.Their indices are P,P[1],...,P[M-1].These M monuments must stay at their original coordinates.The remaining N-M monuments can be moved to any integer coordinates.The monuments do not interfere with each other in any way during movements. The cost of moving a single monument from coordinate a to coordinate b is the absolute difference la-bl.The total cost is the sum of the costs of all the monuments that are moved. Your task is to find the minimum total cost to make the monument positions symmetric about coordinate 0,or determine that it is impossible to achieve such a symmetry under the given constraints. Implementation Details You should implement the following procedure: long long get_cost(std:vector<int>X,std:vector<int>P) X:a non-decreasing array of length N describing the initial coordinates of the monuments. P:a strictly increasing array of length M describing the indices of the ancient monuments. This procedure is called exactly once for each test case. monuments(1 of 4) The procedure should return an integer:the minimum total cost to make the positions symmetric, or-1 if it is impossible. Constraints ·1≤N≤500000 ·0≤M≤N ·-109≤X0≤X[1≤..≤X[W-1≤109 ·0≤P0]<P[1<..<PM-1<N Subtasks Subtask Score Additional Constraints 1 3 M=N 2 4 M=0 3 5 X[P[]]<0for each j such that0<j<M. 4 6 N≤10 5 5 N≤19 6 5 N≤32 7 13 N≤200 6 17 N≤4000 9 13 M≤4000 10 29 No additional constraints. Examples Example 1 Consider the following call: get_cost([-3,-2,1,3],[1,2]) The initial configuration of the monuments is shown in the following figure. monuments(2 of 4) -3 -2-1 1 2 3 There are N=4 monuments,initially located at coordinates [-3,-2,1,3].The indices of the ancient monuments are Po]=1 and P[1]=2.That is,the monuments at coordinates X[P[0]]=-2 and X[P[1]]=1 cannot be moved.The remaining monuments at coordinates -3 and 3 may be moved. To achieve symmetry with minimum total cost,we should move the monuments as follows: Move the monument from coordinate-3 to-1,at a cost of(-3)-(-1)|=2. Move the monument from coordinate 3 to 2,at a cost of |3-2=1. After these moves,the configuration becomes symmetric. -3 -2 -1 1 2 3 The total movement cost is 2+1 =3,so the procedure should return 3. Example 2 Consider the following call: get_cost([2,2,2,3],[1) Here,M =0,which means no monuments are ancient,and all monuments can be moved.One solution with minimum total cost is to move all monuments to coordinate 0.The cost for each monument is: .2-0 =2 for monuments 0,1,and 2. .3-0 =3 for monument 3. monuments(3 of 4) The total cost is 2+2+2+3=9.Hence,the procedure should return 9.Note that there are other solutions with the same total cost. Example 3 Consider the following call: get_cost(I1,2,3,4],[0,1,2,3]) All 4 monuments are ancient and cannot be moved.Since their coordinates are all positive,it is impossible to make the configuration symmetric about 0.Hence,the procedure should return-1. Sample Grader Input format: NM X(0]X[1]··X[N-1] P(0]P[1]···P[M-1] Note that the third line may be empty if M is 0. Output format: Here,C is the value returned by get_cost. monuments(4 of 4) UZBEKISTAN tiling Day 1 Tasks IOI 2026 TASHKENT English(ISC) Tiling Game Barchin and Charos are playing a game on a grid of 2N x 2M unit square cells.The rows are numbered 0 to 2N-1 from top to bottom,and the columns are numbered 0 to 2M-1 from left to right.For 0<i<2N and 0<j<2M,we denote the cell in row i and column j by (i,j). Barchin gives Charos N.M blocks,one by one.Each block is a 2 x 2 square consisting of four 1 x 1 tiles.Barchin has colored every tile of the block either black or white while guaranteeing that at least one tile is white. Charos must place each block on the grid immediately after receiving it,without knowing what blocks she will receive later.Blocks cannot be rotated.Each block must be placed entirely inside the grid,covering exactly four grid cells.Moreover,the top-left tile of each block must cover a cell whose row and column coordinates are both even.Each cell of the grid can be covered by at most one block. Barchin wins the game if,after any block is placed,there exists a 2 x 2 square of cells that is covered by four black tiles.Formally,if cells (a,b),(a+1,b),(a,6+1),(a+1,6+1)are all covered by black tiles for some 0<a<2N-1 and 0<b<2M-1,then Barchin wins.The indices a and b do not need to be even. Charos wins if she places all N.M blocks without Barchin ever winning.Note that placing N.M blocks will completely cover the grid. Your task is to implement a strategy for Charos to win the game.It can be proven that,under the given constraints,Charos can always place the blocks so as to guarantee a win,regardless of the colorings of the blocks she receives later. Implementation Details You should implement two procedures: void init(int N,int M) N:half the number of rows in the grid. M:half the number of columns in the grid. The procedure is called exactly once per test case,at the beginning of the execution of your program. tiling (1 of 5) std:pair<int,int>receive block(int TL,int TR,int BL,int BR) TL,TR,BL,BR:the colors of the top-left,top-right,bottom-left,and bottom-right tiles of the current block,respectively,as shown in the figure below.Each value is either 0(white)or 1(black). This procedure is called exactly N.M times per test case,after the initial call to init. TL TR BL BR This procedure should return a pair of integers(,j),where i is the row coordinate and j is the column coordinate of the cell where the top-left tile of this block should be placed.Both i andj must be even,and the 2 x 2 region covered by the block must not overlap any previously placed block. If receive block ever returns a pair that does not satisfy these requirements,or if after placing the block a 2 x 2 square of cells becomes completely covered by black tiles,the grader will immediately terminate your program and the verdict for the test case will be output isn't correct. The behaviour of the grader is not adaptive.This means that the sequence of blocks Barchin gives to Charos is fixed before init is called. Constraints For each block,let s be the number of black tiles among its four tiles.That is, S=TL+TR+BL+BR. ·1≤N,M≤100 ·0≤S≤3 for every block. tiling (2 of 5) Subtasks Subtask Score Additional Constraints 1 6 S=1 for every block,and N=2. 16 S=3 for every block.N=M,N is even,and each of the four possible 2 block colorings appears exactlytimes. 3 10 S=1 for every block. 4 29 S≤2 for every block. 5 39 No additional constraints. Example Consider a game with N=1 and M =2,so the grid has 2 rows and 4 columns.The grader first calls: init(1,2) Initially,all cells are empty.The grid looks like this: C 123 There are N.M =2 blocks to place.Suppose Barchin gives a block with three black tiles and one white tile at the top-right corner.The grader calls: receive block(1,0,1,1) Charos decides to place this block at the left side of the grid by returning(0,0). The grid now looks like this: tiling (3 of 5) 0123 1 Barchin then gives another block with three black tiles and one white tile at the top-left corner: receive block(0,1,1,1) The only remaining cell with even row and even column that can serve as the top-left corner of a 2 x 2 block is(0,2),so Charos returns (0,2).The grid ends up like this: 01 23 1 No 2 x 2 square is completely covered by black tiles,so Charos has successfully placed all blocks without Barchin ever winning.Charos wins the game. Sample Grader Input format: NM TL[O]TR[O]BL[O]BR[O] TL[1]TR[1]BL[1]BR[1] TL [NM-1]TR[NM-1]BL[NM-1]BR[NM-1] tiling (4 of 5) Output format: R[0]C[0] R[1]C[1] R[NM-1]C[NM-1] Here,Rk]and C[k]are the pair of integers returned by the k-th call to receive block. tiling (5 of 5)