結果
問題 |
No.202 1円玉投げ
|
ユーザー |
![]() |
提出日時 | 2025-08-05 11:14:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 803 ms / 5,000 ms |
コード長 | 3,921 bytes |
コンパイル時間 | 3,646 ms |
コンパイル使用メモリ | 325,508 KB |
実行使用メモリ | 55,124 KB |
最終ジャッジ日時 | 2025-08-05 11:15:07 |
合計ジャッジ時間 | 12,779 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include "bits/stdc++.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/tag_and_trait.hpp> using namespace __gnu_pbds; using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; #define rep(i, m, n) for (ll i = (ll)m; i < (ll)n; i++) #define drep(i, m, n) for (ll i = m - 1; i >= n; i--) #define Endl endl #define all(a) a.begin(), a.end() #define pr(i, j) make_pair(i, j) #define isin(x, l, r) (l <= x && x < r) #define chmin(a, b) a = min(a, b) #define chmax(a, b) a = max(a, b) #define srt(ar) sort(ar.begin(), ar.end()) #define rev(ar) reverse(ar.begin(), ar.end()) #define jge(f, s, t) cout << (f ? s : t) << endl template <typename T> using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define printar(ar) \ do \ { \ for (auto dbg : ar) \ { \ cout << dbg << " "; \ } \ cout << endl; \ } while (0) const ll inf = 1e18; const ld pi = 3.14159265358979; const ld eps = 1e-9; template <class T, ll n, ll idx = 0> auto make_vec(const ll (&d)[n], const T &init) noexcept { if constexpr (idx < n) return std::vector(d[idx], make_vec<T, n, idx + 1>(d, init)); else return init; } template <class T, ll n> auto make_vec(const ll (&d)[n]) noexcept { return make_vec(d, T{}); } //////////////// 以下を貼る //////////////// template <class T> size_t HashCombine(const size_t seed, const T &v) { return seed ^ (std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2)); } /* pair用 */ template <class T, class S> struct std::hash<std::pair<T, S>> { size_t operator()(const std::pair<T, S> &keyval) const noexcept { return HashCombine(std::hash<T>()(keyval.first), keyval.second); } }; /* vector用 */ template <class T> struct std::hash<std::vector<T>> { size_t operator()(const std::vector<T> &keyval) const noexcept { size_t s = 0; for (auto &&v : keyval) s = HashCombine(s, v); return s; } }; /* tuple用 */ template <int N> struct HashTupleCore { template <class Tuple> size_t operator()(const Tuple &keyval) const noexcept { size_t s = HashTupleCore<N - 1>()(keyval); return HashCombine(s, std::get<N - 1>(keyval)); } }; template <> struct HashTupleCore<0> { template <class Tuple> size_t operator()(const Tuple &keyval) const noexcept { return 0; } }; template <class... Args> struct std::hash<std::tuple<Args...>> { size_t operator()(const tuple<Args...> &keyval) const noexcept { return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval); } }; //////////////////////////////////////////// int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin >> n; vector<ll> x(n), y(n); rep(i, 0, n) { cin >> x[i] >> y[i]; } ll ans = 0; unordered_map<pair<ll, ll>, vector<ll>> mp; rep(i, 0, n) { ll X = x[i] / 20; ll Y = y[i] / 20; bool f = false; rep(j, X - 1, X + 2) { rep(k, Y - 1, Y + 2) { rep(l, 0, mp[pr(j, k)].size()) { ll id = mp[pr(j, k)][l]; ll a = x[id] - x[i]; ll b = y[id] - y[i]; if (a * a + b * b < 400) { f = true; break; } } } } if (!f) { ans++; mp[pr(X, Y)].emplace_back(i); } } cout << ans << Endl; }