二次元平面に $N$ 個のロボットがある．
ロボット $k$ の初期位置 $(X_k,Y_k)$ と向いている方向 $D_k$ が与えられる（$D_k$ は上下左右のどれか）．
ロボットは触れると向いている方向にスピード $1$ で動き出す．
ロボットとロボットが同じ座標に行くと，触れるが，移動を邪魔せず，触れる前と同じ方向に動き続ける．
最初，時間 $0$ でロボット $1$ に触れた．
時間 $T$ での各ロボットのいる座標を求める問題．
ちょっと面倒な実装問題．
各ロボットの初期座標に対して，その座標に上下左右に移動するロボットが最初に訪れるまでの時間をダイクストラ法などで求める．
すると，各ロボットがいる場所から，上下左右の四方向それぞれで一番近いロボットの初期位置のみを考えてあげれば良いことになる．
後は，各ロボットが動き出す時間がわかるので，最終位置もすぐわかる．
時間計算量は $O(N \log N)$ 程度．
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T>
struct ullHash{
ull *key; T *val; unsigned memory, size, mask;
void clear(){memset(val,0,size*sizeof(T));}
void clear(int sz){size=1;while(size<sz)size*=2;mask=size-1;clear();}
void init(int mem, int sz){memory=mem;size=1;while(size<sz)size*=2;mask=size-1;if(memory<size)memory=size;key=(ull*)malloc(memory*sizeof(ull));val=(T*)malloc(memory*sizeof(T));if(size)clear();}
int function(ull a){return (a*97531)&mask;}
T get(ull a){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;if(key[i]!=a) return 0;return val[i];}
void set(ull a, T v){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;val[i]=v;}
T increase(ull a, T v = 1){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;return val[i]+=v;}
};
template <class T>
struct heapEx {
int *hp, *place, size; T *val;
void malloc(int N){hp=(int*)std::malloc(N*sizeof(int));place=(int*)std::malloc(N*sizeof(int));val=(T*)std::malloc(N*sizeof(T));}
void free(){free(hp);free(place);free(val);}
void* malloc(int N, void *workMemory){hp=(int*)workMemory;workMemory=(void*)(hp+N);place=(int*)workMemory;workMemory=(void*)(place+N);val=(T*)workMemory;workMemory=(void*)(val+N);return workMemory;}
void init(int N){int i;size=0;rep(i,N)place[i]=-1;}
void up(int n){int m;while(n){m=(n-1)/2;if(val[hp[m]]<=val[hp[n]])break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}}
void down(int n){int m;for(;;){m=2*n+1;if(m>=size)break;if(m+1<size&&val[hp[m]]>val[hp[m+1]])m++;if(val[hp[m]]>=val[hp[n]])break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}}
void change(int n, T v){T f=val[n];val[n]=v;if(place[n]==-1){place[n] = size;hp[size++] = n;up(place[n]);}else{if(f < v) down(place[n]); else if(f > v) up(place[n]);}}
int pop(void){int res=hp[0];place[res]=-1;size--;if(size)hp[0]=hp[size],place[hp[0]]=0,down(0);return res;}
};
ll T;
int N;
ll X[111111], Y[111111];
int xgo[111111], ygo[111111];
char dir[111111];
ll touch[111111][4]; char ddd[5] = "UDLR"; int rev[444];
ll ttm[111111];
int done[111111];
int xsize, ysize;
set< pair<int,int> > xx[111111], yy[111111];
int get_next(int rob, char dir){
int i, j, k;
set< pair<int,int> >::iterator it;
if(dir=='U' || dir=='D'){
k = xgo[rob];
for(;;){
it = xx[k].lower_bound(make_pair((int)Y[rob], rob));
if(it == xx[k].end()) return -1;
if(dir=='U'){
it++;
if(it == xx[k].end()) return -1;
} else {
if(it == xx[k].begin()) return -1;
it--;
}
if(done[it->second]){
xx[k].erase(it);
continue;
}
return it->second;
}
}
if(dir=='L' || dir=='R'){
k = ygo[rob];
for(;;){
it = yy[k].lower_bound(make_pair((int)X[rob], rob));
if(it == yy[k].end()) return -1;
if(dir=='R'){
it++;
if(it == yy[k].end()) return -1;
} else {
if(it == yy[k].begin()) return -1;
it--;
}
if(done[it->second]){
yy[k].erase(it);
continue;
}
return it->second;
}
}
return -1;
}
ll get_dist(int a, int b){
ll res = 0;
res += max(X[a] - X[b], X[b] - X[a]);
res += max(Y[a] - Y[b], Y[b] - Y[a]);
return res;
}
int main(){
int i, j, k, m;
ullHash<int> xind, yind;
heapEx<ll> hp;
reader(&N,&T);
rep(i,N) reader(X+i,Y+i,dir+i);
xind.init(N, N);
yind.init(N, N);
xsize = ysize = 0;
rep(i,N){
k = xind.get(X[i]) - 1;
if(k < 0){ k=xsize++; xind.set(X[i], k+1); }
xgo[i] = k;
k = yind.get(Y[i]) - 1;
if(k < 0){ k=ysize++; yind.set(Y[i], k+1); }
ygo[i] = k;
xx[xgo[i]].insert( make_pair( (int)Y[i], i) );
yy[ygo[i]].insert( make_pair( (int)X[i], i) );
}
hp.malloc(N);
hp.init(N);
hp.change(0, 0);
rep(i,N) ttm[i] = -1;
rep(i,N) rep(j,4) touch[i][j] = -1;
ttm[0] = 0;
rep(i,4) rev[ddd[i]] = i;
while(hp.size){
k = hp.pop();
touch[k][rev[dir[k]]] = ttm[k];
rep(m,4){
if(touch[k][rev[ddd[m]]] == -1) continue;
i = get_next(k, ddd[m]);
if(i >= 0){
if(touch[i][rev[ddd[m]]] == -1 || touch[i][rev[ddd[m]]] >= touch[k][rev[ddd[m]]]+get_dist(k,i)){
touch[i][rev[ddd[m]]] = touch[k][rev[ddd[m]]]+get_dist(k,i);
if(ttm[i] == -1 || ttm[i] >= touch[k][rev[ddd[m]]]+get_dist(k,i)){
ttm[i] = touch[k][rev[ddd[m]]]+get_dist(k,i);
hp.change(i, ttm[i]);
}
}
}
}
done[k] = 1;
}
rep(i,N){
if(ttm[i] < 0) continue;
if(ttm[i] > T) continue;
if(dir[i]=='U') Y[i] += T - ttm[i];
if(dir[i]=='D') Y[i] -= T - ttm[i];
if(dir[i]=='R') X[i] += T - ttm[i];
if(dir[i]=='L') X[i] -= T - ttm[i];
}
rep(i,N) writerLn(X[i],Y[i]);
return 0;
}
Current time: 2024年04月20日00時28分25秒
Last modified: 2015年01月28日00時33分01秒 (by laycrs)
Tags: Competitive_Programming AtCoder New_Year_Contest_2015
トップページに戻る
Logged in as: unknown user (not login)