Codeforces 425 div2 C Strange Radiation

 

Problem - 832C - Codeforces

 

直線上にn人がそれぞれ左か右を向いて立っており、時刻 t=0でそれぞれv[i]で進む。ある整数地点に加速爆弾を置くことができ、時刻t=0で爆発した爆風が左右に速度s( > v)で進み、爆風と向き・位置が一致した人は、速さが s だけ加算される。地点 0, 10^6に誰かが辿り着くまでの最小時間を求める。

 

「ある時間 t 以上ならば(適切な位置に爆弾を置くことで)可能、t 未満なら不可能」

という条件なので時間 t で二分探索。

時間 t を固定すると、例えば正の方向を向いているある人に対し、範囲 [x1 , x2] で爆弾を置けば t 以内に 10^6 に辿り着ける、という範囲が計算できる。

爆弾の位置をX,爆風をs, 人の位置をx, 人の速度をvとして

X + sT = x+ vT

Tが爆風と人が一致する時間になるので、求める条件は

x + vT   +    (v+s)(t-T) >=10^6

これをXについて解けばO(1)で計算できるので、右を向いている人全員に対しこの範囲を計算します。

次に左を向いている人にも同じように計算し、その範囲が右を向いている人の範囲のどれかと被っていたら、その t で達成可能ということがわかります。

範囲計算は、「爆弾がなくても達成可能 (どこに置いてもいいので [0,1000000]が範囲)」や「どこに爆弾をおいても達成不可能(imos法で打ち消しあって欲しいので [1,0]を返す)」などに気をつけます。

右を向いている人全員の範囲を計算するのにimos法と累積和を用いました。

例えば右を向いている人の範囲が [2,5] , [3,6]だとすると、

0 , 0, 1, 0, 0, 0,-1, 0, 0, .... ←[2,5]の範囲をusedに記憶

0 , 0, 1, 1, 0, 0,-1,-1, 0, .... ←[3,6]の範囲を記憶

0 , 0, 1, 2, 2, 2, 1, 0, 0, .... ←imos法により、地点がいずれかの範囲内であれば0より大きい

0 , 0, 1, 3, 5, 7, 8, 8, 8, .... ←累積和により、[ x, y ] に範囲が含まれているかどうかを sum[y] - sum[x -1] >0 で調べられる

 

#include <bits/stdc++.h>
#define REP(i,n) for(LL i=0;i<(LL)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

//右を向いている人の範囲計算
pair<LL,LL> minX(LL s,long double t,LL x,LL v){
if((x+v*t)>=1000000)return make_pair(0,1000000);
if((x+(v+s)*t)<1000000)return make_pair(1,0);
long double res=(0.0 + (s-v)*1000000 + x*v -(0.0 + s*s -v*v)*t +s -1)/s;
return make_pair(max(0LL,(LL)res),x);
}

//左を向いている人の範囲計算
pair<LL,LL> maxX(LL s,long double t,LL x,LL v){
if((x-v*t)<=0)return make_pair(0,1000000);
if((x-(s+v)*t)>0)return make_pair(1,0);
long double res=(0.0 + x*v +(0.0 + s*s -v*v)*t)/s;
return make_pair(x,min((LL)res,1000000LL));
}



int main(){

LL n;
LL s;
cin>>n>>s;
LL x[n],v[n],t[n];
REP(i,n)cin>>x[i]>>v[i]>>t[i];

long double left =0;
long double right=1000000;
long double center;

long double err=1e-10;


LL used[1000002];
bool isRight=false;

while(true){
isRight=false;
center=(left+right)/2;
fill_n(used,1000001,0);
REP(i,n) {
if (t[i] == 2) {
pair<LL, LL> pa = minX(s, center, x[i], v[i]);
used[pa.first]++;
used[pa.second + 1]--;
}
}
REP(i,1000001)used[i+1]+=used[i];//imos法
REP(i,1000001)used[i+1]+=used[i];//累積和
REP(i,n){
if(t[i]==1){
pair<LL,LL> pa = maxX(s,center,x[i],v[i]);
if(pa.first==0){
if(used[pa.second]>0)isRight=true;
}else{
if(used[pa.second]-used[pa.first-1]>0)isRight=true;
}
}
}
if(isRight)right=center;
else left=center;

if(abs((left+right)/2 -center)< err)break;
}

cout<<fixed<<setprecision(20)<<right<<endl;

return 0;
}