Submission #2869687


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

constexpr int mod = 1e9 + 7;
constexpr int32_t inf = 1001001001;
constexpr int64_t infll = 1001001001001001001ll;
constexpr int dx[] = {0, -1, 1, 0, -1, 1, -1, 1}, dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const string YES = "YES", NO = "NO", Yes = "Yes", No = "No", yes = "yes", no = "no";

// clang-format off
// ostream &operator<<(ostream &os, __int128_t value) { if (ostream::sentry(os)) { __uint128_t tmp = value < 0 ? -value : value; char buffer[64]; char *d = end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); }} return os; }
// istream &operator>>(istream &is, __int128_t &value) { string in; is >> in; value = 0; for (const char &c : in) { if ('0' <= c && c <= '9') value = 10 * value + (c - '0'); } if (in[0] == '-') value *= -1; return is; }
// ostream &operator<<(ostream &os, __uint128_t value) { if (ostream::sentry(os)) { char buffer[64]; char *d = end(buffer); do { --d; *d = "0123456789"[value % 10]; value /= 10; } while (value != 0); int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); }} return os; }
// istream &operator>>(istream &is, __uint128_t &value) { string in; is >> in; value = 0; for (const char &c : in) { if ('0' <= c && c <= '9') value = 10 * value + (c - '0'); } return is; }
template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { os << v[0]; for (int i = 1; i < v.size(); ++i) os << " " << v[i]; return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.fs << " " << p.sc; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.fs >> p.sc; return is; }

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(15); cerr << fixed << setprecision(10); } } iosetup;

inline int64_t in() { int64_t x = 0; cin >> x; return x; }

template <typename T> void sort(vector<T> &v) { sort(all(v)); }
template <typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on

signed main(int argc, char *argv[]) {
  double r = 10, l = 0.5 * r * acos(-1);

  pair<int64_t, int64_t> s, g;
  cin >> s >> g;

  int n = in();
  vector<pair<int64_t, int64_t>> v;
  for (int i = 0; i < n; ++i) {
    int x = in(), y = in();
    if (min(s.fs, g.fs) <= x && x <= max(s.fs, g.fs) && min(s.sc, g.sc) <= y && y <= max(s.sc, g.sc)) {
      v.pb(x, y);
    }
  }

  auto lis = [&](bool f) {
    vector<int64_t> dp(v.size(), (f ? 1 : -1) * inf);
    auto comp = [&](int64_t a, int64_t b) { return (f ? a < b : b < a); };
    for (auto i : v) *lower_bound(all(dp), i.fs, comp) = i.fs;
    return lower_bound(all(dp), (f ? 1 : -1) * inf, comp) - dp.begin();
  };

  auto solve = [&]() {
    double res = 100 * (abs(s.fs - g.fs) + abs(s.sc - g.sc));
    int n = lis(min(s.fs, g.fs) == min(s, g).fs && min(s.sc, g.sc) == min(s, g).sc);
    if (n == min(abs(s.fs - g.fs), abs(s.sc - g.sc)) + 1) {
      cerr << "+++ukunichia+++" << endl;
      res -= 2 * n * r - (n + 1) * l;
    } else {
      res -= 2 * n * r - n * l;
    }

    return res;
  };

  cout << solve() << endl;
}

Submission Info

Submission Time
Task C - Fountain Walk
User Luzhiled
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3981 Byte
Status WA
Exec Time 55 ms
Memory 6384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 21
WA × 26
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt WA 1 ms 256 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt AC 14 ms 256 KB
subtask_1_10.txt AC 30 ms 256 KB
subtask_1_11.txt WA 8 ms 256 KB
subtask_1_12.txt WA 52 ms 5872 KB
subtask_1_13.txt AC 30 ms 256 KB
subtask_1_14.txt WA 14 ms 256 KB
subtask_1_15.txt WA 7 ms 256 KB
subtask_1_16.txt WA 55 ms 4972 KB
subtask_1_17.txt AC 24 ms 256 KB
subtask_1_18.txt WA 20 ms 256 KB
subtask_1_19.txt WA 19 ms 384 KB
subtask_1_20.txt WA 50 ms 6384 KB
subtask_1_21.txt WA 52 ms 5488 KB
subtask_1_22.txt WA 51 ms 4972 KB
subtask_1_23.txt WA 52 ms 5104 KB
subtask_1_24.txt AC 1 ms 256 KB
subtask_1_25.txt AC 1 ms 256 KB
subtask_1_26.txt AC 1 ms 256 KB
subtask_1_27.txt AC 1 ms 256 KB
subtask_1_28.txt WA 35 ms 512 KB
subtask_1_29.txt WA 38 ms 512 KB
subtask_1_30.txt WA 52 ms 5232 KB
subtask_1_31.txt WA 47 ms 6256 KB
subtask_1_32.txt WA 47 ms 6128 KB
subtask_1_33.txt WA 47 ms 5488 KB
subtask_1_34.txt WA 47 ms 5488 KB
subtask_1_35.txt WA 52 ms 5744 KB
subtask_1_36.txt WA 52 ms 4972 KB
subtask_1_37.txt WA 52 ms 5488 KB
subtask_1_38.txt WA 52 ms 5232 KB
subtask_1_39.txt WA 52 ms 5616 KB
subtask_1_40.txt WA 52 ms 4972 KB
subtask_1_41.txt WA 52 ms 5488 KB