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 |
|
|
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 |