Submission #15446907


Source Code Expand

Copy
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
#define SZ(x) (int)((x).size())

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

int main() {
  int n;
  scanf("%d", &n);
  vector<ii> L, R, U, D;
  for (int i = 0; i < n; ++i) {
    static char s[10];
    int x, y;
    scanf("%d%d%s", &x, &y, s);
    if (s[0] == 'L') {
      L.push_back({x, y});
    } else if (s[0] == 'R') {
      R.push_back({x, y});
    } else if (s[0] == 'U') {
      U.push_back({x, y});
    } else {
      D.push_back({x, y});
    }
  }
  int ret = INF;
  // U collide with D
  sort(U.begin(), U.end());
  sort(D.begin(), D.end());
  for (int i = 0, j = 0, ni, nj; i < SZ(U) && j < SZ(D); ) {
    if (U[i].first < D[j].first) {
      ++i;
    } else if (U[i].first > D[j].first) {
      ++j;
    } else {
      for (ni = i + 1; ni < SZ(U) && U[ni].first == U[i].first; ++ni);
      for (nj = j + 1; nj < SZ(D) && D[nj].first == D[j].first; ++nj);
      for (int k = i; k < ni; ++k) {
        int pos = upper_bound(D.begin() + j, D.begin() + nj, U[k]) - D.begin();
        if (pos != nj) ret = min(ret, D[pos].second - U[k].second);
      }
      i = ni;
      j = nj;
    }
  }
  // L collide with R
  sort(L.begin(), L.end(), [](const ii& u, const ii& v) {
                             return u.second < v.second ||
                                               (u.second == v.second && u.first < v.first);
                           });
  sort(R.begin(), R.end(), [](const ii& u, const ii& v) {
                             return u.second < v.second ||
                                               (u.second == v.second && u.first < v.first);
                           });
  for (int i = 0, j = 0, ni, nj; i < SZ(L) && j < SZ(R); ) {
    if (L[i].second < R[j].second) {
      ++i;
    } else if (L[i].second > R[j].second) {
      ++j;
    } else {
      for (ni = i + 1; ni < SZ(L) && L[ni].second == L[i].second; ++ni);
      for (nj = j + 1; nj < SZ(R) && R[nj].second == R[j].second; ++nj);
      for (int k = j; k < nj; ++k) {
        int pos = upper_bound(L.begin() + i, L.begin() + ni, R[k]) - L.begin();
        if (pos != ni) ret = min(ret, L[pos].first - R[k].first);
      }
      i = ni;
      j = nj;
    }
  }
  // D collide with L
  {
    map<int, set<int>> mL;
    for (auto& [x, y] : L) mL[x + y].insert(x);
    for (auto& [x, y] : D) {
      if (!mL.count(x + y)) continue;
      auto& v = mL[x + y];
      auto it = v.upper_bound(x);
      if (it != v.end()) ret = min(ret, 2 * (*it - x));
    }
  }
  // D collide with R
  {
    map<int, set<int>> mD;
    for (auto& [x, y] : D) mD[x - y].insert(x);
    for (auto& [x, y] : R) {
      if (!mD.count(x - y)) continue;
      auto& v = mD[x - y];
      auto it = v.upper_bound(x);
      if (it != v.end()) ret = min(ret, 2 * (*it - x));
    }
  }
  // U collide with L
  {
    map<int, set<int>> mL;
    for (auto& [x, y] : L) mL[x - y].insert(x);
    for (auto& [x, y] : U) {
      if (!mL.count(x - y)) continue;
      auto& v = mL[x - y];
      auto it = v.upper_bound(x);
      if (it != v.end()) ret = min(ret, 2 * (*it - x));
    }
  }
  // U collide with R
  {
    map<int, set<int>> mU;
    for (auto& [x, y] : U) mU[x + y].insert(x);
    for (auto& [x, y] : R) {
      if (!mU.count(x + y)) continue;
      auto& v = mU[x + y];
      auto it = v.upper_bound(x);
      if (it != v.end()) ret = min(ret, 2 * (*it - x));
    }
  }
  if (ret == INF) {
    puts("SAFE");
  } else {
    printf("%d\n", ret * 5);
  }

  return 0;
}

Submission Info

Submission Time
Task F - Air Safety
User cuiaoxiang
Language C++ (Clang 10.0.0)
Score 600
Code Size 5951 Byte
Status AC
Exec Time 193 ms
Memory 29096 KB

Compile Error

./Main.cpp:78:11: warning: unused variable 'MOD' [-Wunused-const-variable]
const int MOD = 1e9 + 7;
          ^
1 warning generated.

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 57
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in48.txt, in49.txt, in50.txt, in51.txt, in52.txt, in53.txt, in54.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
in01.txt AC 11 ms 3076 KB
in02.txt AC 2 ms 3108 KB
in03.txt AC 2 ms 3048 KB
in04.txt AC 4 ms 3120 KB
in05.txt AC 7 ms 3380 KB
in06.txt AC 21 ms 3920 KB
in07.txt AC 33 ms 4752 KB
in08.txt AC 74 ms 6144 KB
in09.txt AC 173 ms 10360 KB
in10.txt AC 122 ms 6764 KB
in11.txt AC 5 ms 2912 KB
in12.txt AC 4 ms 3204 KB
in13.txt AC 19 ms 5124 KB
in14.txt AC 193 ms 18764 KB
in15.txt AC 1 ms 3092 KB
in16.txt AC 109 ms 12332 KB
in17.txt AC 2 ms 3048 KB
in18.txt AC 3 ms 3164 KB
in19.txt AC 23 ms 4312 KB
in20.txt AC 150 ms 12192 KB
in21.txt AC 6 ms 3236 KB
in22.txt AC 4 ms 3344 KB
in23.txt AC 27 ms 4196 KB
in24.txt AC 125 ms 9568 KB
in25.txt AC 6 ms 3028 KB
in26.txt AC 136 ms 14392 KB
in27.txt AC 5 ms 3044 KB
in28.txt AC 125 ms 14612 KB
in29.txt AC 2 ms 3028 KB
in30.txt AC 125 ms 14316 KB
in31.txt AC 3 ms 3176 KB
in32.txt AC 131 ms 20308 KB
in33.txt AC 7 ms 3048 KB
in34.txt AC 116 ms 12208 KB
in35.txt AC 7 ms 3036 KB
in36.txt AC 103 ms 12320 KB
in37.txt AC 4 ms 2908 KB
in38.txt AC 117 ms 10508 KB
in39.txt AC 4 ms 3084 KB
in40.txt AC 97 ms 10384 KB
in41.txt AC 100 ms 16924 KB
in42.txt AC 118 ms 9076 KB
in43.txt AC 88 ms 7488 KB
in44.txt AC 131 ms 29096 KB
in45.txt AC 96 ms 6428 KB
in46.txt AC 86 ms 9156 KB
in47.txt AC 100 ms 16812 KB
in48.txt AC 121 ms 10404 KB
in49.txt AC 2 ms 2908 KB
in50.txt AC 2 ms 3236 KB
in51.txt AC 3 ms 3148 KB
in52.txt AC 2 ms 3232 KB
in53.txt AC 2 ms 2916 KB
in54.txt AC 3 ms 3232 KB
sample_01.txt AC 3 ms 3116 KB
sample_02.txt AC 2 ms 3000 KB
sample_03.txt AC 2 ms 3120 KB