企业官网建设流程全解析

P12016 [NOISG 2025 Finals] 震踏

题目描述

Bunnyland 有广阔的田野，Bunnyland 矮兔（一种本地兔子物种）在其中自由活动。其中一个田野可以建模为一个109×10910^9 \times 10^9109×109的网格单元。网格的行从北到南编号为111到10910^9109，网格的列从西到东编号为111到10910^9109。我们将网格中位于第rrr行、第ccc列的单元格称为单元格(r,c)(r, c)(r,c)。

在这片田野中，有nnn只兔子，编号从111到nnn。第iii只兔子最初位于单元格(r[i],c[i])(r[i], c[i])(r[i],c[i])。最初没有两只兔子位于同一个单元格。

当兔子感到烦躁时，它们会抬起后腿并踢打地面，这一动作被称为震踏。这nnn只兔子将执行一系列mmm次震踏。在第jjj秒开始时，编号为t[j]t[j]t[j]的兔子会进行震踏。当一只兔子震踏时，所有其他兔子都会远离震踏的兔子。

具体来说，当兔子 A 震踏时，兔子 B 将按照以下方式移动：

• 如果 A 和 B 之间的行数小于列数，则 B 将在列方向上远离 A 两列。
• 如果 A 和 B 之间的行数等于列数，则 B 将在列方向和行方向各远离 A 一格。
• 如果 A 和 B 之间的行数大于列数，则 B 将在行方向上远离 A 两行。

可以证明，在震踏发生后，兔子的位置仍然是互不相同的。

兔子 Benson 在退休后寻找它的同类，但由于震踏的发生，兔子们四散开来。请帮助 Benson 确定在所有震踏发生后nnn只兔子的最终位置！

可以保证，在震踏序列过程中，兔子不会离开网格。你也可以假设，兔子在任何情况下都不会移动，除了震踏。

输入格式

你的程序必须从标准输入读取数据。

输入的第一行包含两个由空格分隔的整数nnn和mmm。

接下来的nnn行输入中，每行包含两个由空格分隔的整数。这些整数分别是r[i]r[i]r[i]和c[i]c[i]c[i]，表示第iii只兔子的初始位置。

输入的最后一行包含mmm个由空格分隔的整数t[1],t[2],…,t[m]t[1], t[2], \ldots, t[m]t[1],t[2],…,t[m]。

输出格式

你的程序必须向标准输出打印结果。

输出应包含nnn行。第iii行应包含两个由空格分隔的整数，表示所有震踏发生后，第iii只兔子所在的行和列。

输入输出样例 #1

输入 #1

2 1 1 1 2 2 1

输出 #1

1 1 3 3

输入输出样例 #2

输入 #2

13 1 7 7 3 7 4 4 4 10 5 6 6 4 6 8 8 7 8 10 9 3 9 5 9 9 10 6 1

输出 #2

7 7 1 7 3 3 3 11 3 6 6 2 5 9 10 7 8 12 9 1 10 4 10 10 12 6

输入输出样例 #3

输入 #3

3 2 1 10 1 20 1 30 1 3

输出 #3

1 8 1 20 1 32

说明/提示

子任务

对于所有测试用例，输入将满足以下约束条件：

• 1≤n,m≤500 0001 \leq n, m \leq 500\,0001≤n,m≤500000
• 对于所有1≤i≤n1 \leq i \leq n1≤i≤n，有1≤r[i],c[i]≤1091 \leq r[i], c[i] \leq 10^91≤r[i],c[i]≤109
• 对于所有1≤j≤m1 \leq j \leq m1≤j≤m，有1≤t[j]≤n1 \leq t[j] \leq n1≤t[j]≤n
• 对于所有i≠ji \neq ji=j，有(ri,ci)≠(rj,cj)(r_i, c_i) \neq (r_j, c_j)(ri​,ci​)=(rj​,cj​)
• 可以保证，在震踏序列过程中，兔子不会离开网格。

你的程序将在满足以下特殊性质的输入数据上进行测试：

样例 1 解释

此测试用例适用于子任务1,3,4,51, 3, 4, 51,3,4,5。

兔子111处于单元格(1,1)(1, 1)(1,1)，兔子222处于单元格(2,2)(2, 2)(2,2)。

由于兔子111和兔子222之间的行数等于列数，因此当兔子111震踏时，兔子222会在东南方向各远离一格，最终到达单元格(3,3)(3, 3)(3,3)。震踏的兔子111位置保持不变。

样例 2 解释

此样例适用于子任务1,3,4,51, 3, 4, 51,3,4,5。

题目中的图示对应于此测试用例。蓝色箭头显示了当编号为111的兔子（位于单元格(7,7)(7, 7)(7,7)）震踏时，其他兔子的移动方式。

样例 3 解释

此样例适用于所有子任务。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=5e5+5,INF=1e9;structrabbit{intr,c;}r[MAXN];structline{intk,sp;//k:坐标 sp:兔子编号booloperator<(constline&a)const{returnk<a.k;}booloperator<=(constline&a)const{returnk<=a.k;}};intn,m,cfa[MAXN],cfb[MAXN],_a[MAXN],_b[MAXN];vector<line>a,b;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(inti=1;i<=n;i++){cin>>r[i].r>>r[i].c;a.push_back((line){r[i].r+r[i].c,i});b.push_back((line){INF-r[i].r+r[i].c,i});}sort(a.begin(),a.end());sort(b.begin(),b.end());for(inti=1,t;i<=m;i++){cin>>t;intkta=r[t].r+r[t].c,ktb=INF-r[t].r+r[t].c;intla=lower_bound(a.begin(),a.end(),(line){kta,1})-a.begin(),ra=upper_bound(a.begin(),a.end(),(line){kta,1})-a.begin(),lb=lower_bound(b.begin(),b.end(),(line){ktb,1})-b.begin(),rb=upper_bound(b.begin(),b.end(),(line){ktb,1})-b.begin();cfa[0]+=-1,cfa[la]+=1;cfa[ra]+=1,cfa[n]+=-1;cfb[0]+=-1,cfb[lb]+=1;cfb[rb]+=1,cfb[n]+=-1;}for(inti=0;i<n;i++){cfa[i]+=cfa[i-1],cfb[i]+=cfb[i-1];_a[a[i].sp]=cfa[i],_b[b[i].sp]=cfb[i];}for(inti=1;i<=n;i++){r[i].r+=_a[i]-_b[i];r[i].c+=_a[i]+_b[i];cout<<r[i].r<<" "<<r[i].c<<endl;}}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容