有许多蚂蚁在一根无限长的木棍上,每一只蚂蚁都有一个初始位置和初始朝向(任意两只蚂蚁的初始位置不同)。蚂蚁们以每秒一个单位的速度向前移动,当两只蚂蚁相遇时,它们会掉头(掉头时间忽略不计)。现给出每只蚂蚁的初始位置和初始朝向,请你计算出它们在 t 秒后的位置和朝向。
通过观察我们可以发现两个性质: 1.如果两只蚂蚁碰头以后,我们可以不让他们掉头,而是交换两只蚂蚁的灵魂,让他们继续往前走 2.在限定秒速走完以后,每个蚂蚁仍是按照初始时的顺序排列 明白这两个性质后就容易想了,我们可以先按初始位置排序,然后模拟每只蚂蚁的行走轨迹,再使用一个数组来记录排序后所对应的下标,判断是否正在掉头可以使用map数组,如果一个点上有多只蚂蚁,则它们正在掉头。这样就不用考虑掉头,大大简化了问题。
#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=2*1e5+10;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int n,t;
struct node{
int point,dir,idx;
}Node[N];
bool cmp(node A,node B){
return A.point<B.point;
}
map<int,int> cnt;
map<int,int> pos;
void solve(){
cin>>n>>t;
for(int i=0;i<n;i++){
cin>>Node[i].point>>Node[i].dir;
Node[i].idx=i;
}
sort(Node,Node+n,cmp);
for(int i=0;i<n;i++){
Node[i].point+=Node[i].dir*t;
cnt[Node[i].point]++;
pos[Node[i].idx]=i;
}
sort(Node,Node+n,cmp);
for(int i=0;i<n;i++){
cout<<Node[pos[i]].point<<' ';
if(cnt[Node[pos[i]].point]!=1) cout<<0<<endl;
else cout<<Node[pos[i]].dir<<endl;
}
}
int main(){
IOS;
solve();
return 0;
}