Robots

input/code.cpp: In function 'int main()':
input/code.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < n; ++i){
                      ^
input/code.cpp:52:21: warning: array subscript has type 'char' [-Wchar-subscripts]
     d[i] = trans[fak];
                     ^
input/code.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < n; ++i){
                      ^
input/code.cpp:110:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < n; ++i){
                      ^
input/code.cpp:126:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(dis > t){
              ^
input/code.cpp:135:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < n; ++i){
                      ^

#include <bits/stdc++.h>

#define i64 long long
#define u64 unsigned long long
#define i32 int
#define u32 unsigned int

#define pii pair<int, int>
#define pll pair<long long, long long>

#define ld long double
#define defmod 1000000007

#define mati64(a,b) vector<vector<i64>>(a, vector<i64>(b, 0));
#define sit set<i64>::iterator
using namespace std;
u64 n, t; 
int d[101010];
i64 x[101010], y[101010];
int trans[1010];
int fuckme[10][2];
map<i64, set<i64>> rip[4];
vector<int> v[101010];
vector<int> v2[101010];
map<pair<pair<i64, i64>, int>, int> id;

i64 manh(int i, int j){
  return abs(x[i]-x[j])+abs(y[i]-y[j]);
}
int main(){
  //set<int> kk;
  //kk.insert(0);
  //cout <<"wtf"<< *(--kk.lower_bound(1)) << endl;
  trans['U'] = 0;
  trans['D'] = 2;
  trans['R'] = 1;
  trans['L'] = 3;
  fuckme[0][0] = 0;
  fuckme[0][1] = 1;
  fuckme[1][0] = 1;
  fuckme[1][1] = 0;
  fuckme[2][0] = 0;
  fuckme[2][1] = -1;
  fuckme[3][0] = -1;
  fuckme[3][1] = 0;
  cin.sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> t;
  for(int i = 0; i < n; ++i){
    char fak;
    cin >> x[i] >> y[i] >> fak;
    d[i] = trans[fak];
    id[{{x[i], y[i]}, d[i]}] = i;
    if(d[i] == 0 || d[i] == 2){
      //cout << "dir " << d[i] << " x " << x[i] << " y " << y[i] << endl; 
      rip[d[i]][x[i]].insert(y[i]);
    }
    else{
      //cout << "dir " << d[i] << " y " << y[i] << " x " << x[i] << endl; 
      rip[d[i]][y[i]].insert(x[i]);
    }
  }
  
  for(int i = 0; i < n; ++i){
    
    if(rip[0][x[i]].size()){
      sit lol = rip[0][x[i]].lower_bound(y[i]);
      //cout << "U cont " << 0 << " x " << x[i] << " ";
      //for(auto f: rip[0][x[i]])
	//cout << f << " ";
      //cout << endl;
      //cout << "U loy " << *lol << endl;
      if((*lol) == y[i] || lol == rip[0][x[i]].end())
	--lol;
      //cout << "U loy " << *lol << endl;
      if(rip[0][x[i]].count(*lol) && *lol < y[i])
	v[i].push_back(id[{{x[i], *lol}, 0}]);
    }
    if(rip[2][x[i]].size()){
      sit lol = rip[2][x[i]].upper_bound(y[i]);
      if((*lol) == y[i])
	++lol;
      if(rip[2][x[i]].count(*lol) && *lol > y[i])
	v[i].push_back(id[{{x[i], *lol}, 2}]);
    }
    if(rip[1][y[i]].size()){
      sit lol = rip[1][y[i]].lower_bound(x[i]);
      //cout << "U cont " << 0 << " x " << x[i] << " ";
      //for(auto f: rip[0][x[i]])
	//cout << f << " ";
      //cout << endl;
      //cout << "U loy " << *lol << endl;
      if((*lol) == x[i] || lol == rip[1][y[i]].end())
	--lol;
      if(rip[1][y[i]].count(*lol) && *lol < x[i])
	v[i].push_back(id[{{*lol, y[i]}, 1}]);
    }
    if(rip[3][y[i]].size()){
      sit lol = rip[3][y[i]].upper_bound(x[i]);
      if((*lol) == x[i])
	++lol;
      if(rip[3][y[i]].count(*lol) && *lol > x[i])
	v[i].push_back(id[{{*lol, y[i]}, 3}]);
    }
    //cout << i << " paas ";
    //for(auto f: v[i])
    //  cout << f<< " ";
    //cout << endl;
  }
  for(int i = 0; i < n; ++i){
    for(auto f: v[i])
      v2[f].push_back(i);
    
  }
  priority_queue<pair<i64, int>> q;
  q.push({0, 0});
  pair<i64, i64> ans[101010];
  bool d1[101010] = {0};
  while(!q.empty()){
    int cur = q.top().second;
    i64 dis = -q.top().first;
    q.pop();
    if(d1[cur])
      continue;
    d1[cur] = 1;
    if(dis > t){
      ans[cur] = {x[cur], y[cur]};
    }
    else{
      ans[cur] = {x[cur]+fuckme[d[cur]][0]*(t-dis), y[cur]+fuckme[d[cur]][1]*(t-dis)};
    }
    for(auto f: v2[cur])
      q.push({-(dis+manh(cur, f)), f});
  }
  for(int i = 0; i < n; ++i){
    if(!d1[i])
      cout << x[i] << " " << y[i] << endl;
    else
      cout << ans[i].first << " " << ans[i].second << endl;
  }
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: ACCEPTED

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: ACCEPTED

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: ACCEPTED

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER