結果
問題 | No.2510 Six Cube Sum Counting |
ユーザー |
|
提出日時 | 2023-10-20 23:07:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 741 ms / 4,000 ms |
コード長 | 13,743 bytes |
コンパイル時間 | 2,157 ms |
コンパイル使用メモリ | 207,516 KB |
最終ジャッジ日時 | 2025-02-17 10:46:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
コンパイルメッセージ
main.cpp:70:7: warning: ‘template<class _Category, class _Tp, class _Distance, class _Pointer, class _Reference> struct std::iterator’ is deprecated [-Wdeprecated-declarations] 70 | : iterator<bidirectional_iterator_tag, Data, ptrdiff_t, Data*, Data&> { | ^~~~~~~~ In file included from /usr/include/c++/13/bits/stl_algobase.h:65, from /usr/include/c++/13/algorithm:60, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51, from main.cpp:1: /usr/include/c++/13/bits/stl_iterator_base_types.h:127:34: note: declared here 127 | struct _GLIBCXX17_DEPRECATED iterator | ^~~~~~~~ main.cpp:72:7: warning: ‘template<class _Category, class _Tp, class _Distance, class _Pointer, class _Reference> struct std::iterator’ is deprecated [-Wdeprecated-declarations] 72 | iterator<bidirectional_iterator_tag, Data, ptrdiff_t, Data*, Data&>; | ^~~~~~~~ /usr/include/c++/13/bits/stl_iterator_base_types.h:127:34: note: declared here 127 | struct _GLIBCXX17_DEPRECATED iterator | ^~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;#define overload4(_1, _2, _3, _4, name, ...) name#define rep1(n) for(int i = 0; i < (int)(n); ++i)#define rep2(i, n) for(int i = 0; i < (int)(n); ++i)#define rep3(i, a, b) for(int i = (a); i < (int)(b); ++i)#define rep4(i, a, b, c) for(int i = (a); i < (int)(b); i += (c))#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; --i)#define ALL(a) a.begin(), a.end()#define Sort(a) sort(a.begin(), a.end())#define RSort(a) sort(a.rbegin(), a.rend())typedef long long int ll;typedef unsigned long long ul;typedef long double ld;typedef vector<int> vi;typedef vector<long long> vll;typedef vector<char> vc;typedef vector<string> vst;typedef vector<double> vd;typedef vector<long double> vld;typedef pair<long long, long long> P;template<class T> long long sum(const T& a){ return accumulate(a.begin(), a.end(), 0LL); }template<class T> auto min(const T& a){ return *min_element(a.begin(), a.end()); }template<class T> auto max(const T& a){ return *max_element(a.begin(), a.end()); }const long long MINF = 0x7fffffffffff;const long long INF = 0x1fffffffffffffff;const long long MOD = 998244353;const long double EPS = 1e-9;const long double PI = acos(-1);template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p){ is >> p.first >> p.second; return is; }template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){ os << "(" << p.first << ", " << p.second << ")"; returnos; }template<typename T> istream &operator>>(istream &is, vector<T> &v){ for(T &in : v) is >> in; return is; }template<typename T> ostream &operator<<(ostream &os, const vector<T> &v){ for(int i = 0; i < (int) v.size(); ++i){ os << v[i] << (i + 1 != (int) v.size() ? " " : ""); } return os; }template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp){ for(auto &[key, val] : mp){ os << key << ":" << val << " ";} return os; }template <typename T> ostream &operator<<(ostream &os, const set<T> &st){ auto itr = st.begin(); for(int i = 0; i < (int)st.size(); ++i){ os << *itr<< (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st){ auto itr = st.begin(); for(int i = 0; i < (int)st.size(); ++i){ os <<*itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }template <typename T> ostream &operator<<(ostream &os, queue<T> q){ while(q.size()){ os << q.front() << " "; q.pop(); } return os; }template <typename T> ostream &operator<<(ostream &os, deque<T> q){ while(q.size()){ os << q.front() << " "; q.pop_front(); } return os; }template <typename T> ostream &operator<<(ostream &os, stack<T> st){ while(st.size()){ os << st.top() << " "; st.pop(); } return os; }template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq){ while(pq.size()){ os<< pq.top() << " "; pq.pop(); } return os; }template<class T, class U> inline T vin(T& vec, U n) { vec.resize(n); for(int i = 0; i < (int) n; ++i) cin >> vec[i]; return vec; }template<class T> inline void vout(T vec, string s = "\n"){ for(auto x : vec) cout << x << s; }template<class... T> void in(T&... a){ (cin >> ... >> a); }void out(){ cout << '\n'; }template<class T, class... Ts> void out(const T& a, const Ts&... b){ cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; }template<class T, class U> void inGraph(vector<vector<T>>& G, U n, U m, bool directed = false){ G.resize(n); for(int i = 0; i < m; ++i){ int a, b;cin >> a >> b; a--, b--; G[a].push_back(b); if(!directed) G[b].push_back(a); } }// https://nyaannyaan.github.io/library/hashmap/hashmap.hppnamespace HashMapImpl {using u32 = uint32_t;using u64 = uint64_t;template <typename Key, typename Data>struct HashMapBase;template <typename Key, typename Data>struct itrB: iterator<bidirectional_iterator_tag, Data, ptrdiff_t, Data*, Data&> {using base =iterator<bidirectional_iterator_tag, Data, ptrdiff_t, Data*, Data&>;using ptr = typename base::pointer;using ref = typename base::reference;u32 i;HashMapBase<Key, Data>* p;explicit constexpr itrB() : i(0), p(nullptr) {}explicit constexpr itrB(u32 _i, HashMapBase<Key, Data>* _p) : i(_i), p(_p) {}explicit constexpr itrB(u32 _i, const HashMapBase<Key, Data>* _p): i(_i), p(const_cast<HashMapBase<Key, Data>*>(_p)) {}friend void swap(itrB& l, itrB& r) { swap(l.i, r.i), swap(l.p, r.p); }friend bool operator==(const itrB& l, const itrB& r) { return l.i == r.i; }friend bool operator!=(const itrB& l, const itrB& r) { return l.i != r.i; }const ref operator*() const {return const_cast<const HashMapBase<Key, Data>*>(p)->data[i];}ref operator*() { return p->data[i]; }ptr operator->() const { return &(p->data[i]); }itrB& operator++() {assert(i != p->cap && "itr::operator++()");do {i++;if (i == p->cap) break;if (p->occupied_flag[i] && !p->deleted_flag[i]) break;} while (true);return (*this);}itrB operator++(int) {itrB it(*this);++(*this);return it;}itrB& operator--() {do {i--;if (p->occupied_flag[i] && !p->deleted_flag[i]) break;assert(i != 0 && "itr::operator--()");} while (true);return (*this);}itrB operator--(int) {itrB it(*this);--(*this);return it;}};template <typename Key, typename Data>struct HashMapBase {using u32 = uint32_t;using u64 = uint64_t;using iterator = itrB<Key, Data>;using itr = iterator;protected:template <typename K>inline u64 randomized(const K& key) const {return u64(key) ^ r;}template <typename K,enable_if_t<is_same<K, Key>::value, nullptr_t> = nullptr,enable_if_t<is_integral<K>::value, nullptr_t> = nullptr>inline u32 inner_hash(const K& key) const {return (randomized(key) * 11995408973635179863ULL) >> shift;}template <typename K, enable_if_t<is_same<K, Key>::value, nullptr_t> = nullptr,enable_if_t<is_integral<decltype(K::first)>::value, nullptr_t> = nullptr,enable_if_t<is_integral<decltype(K::second)>::value, nullptr_t> = nullptr>inline u32 inner_hash(const K& key) const {u64 a = randomized(key.first), b = randomized(key.second);a *= 11995408973635179863ULL;b *= 10150724397891781847ULL;return (a + b) >> shift;}template <typename K,enable_if_t<is_same<K, Key>::value, nullptr_t> = nullptr,enable_if_t<is_integral<typename K::value_type>::value, nullptr_t> =nullptr>inline u32 inner_hash(const K& key) const {static constexpr u64 mod = (1LL << 61) - 1;static constexpr u64 base = 950699498548472943ULL;u64 res = 0;for (auto& elem : key) {__uint128_t x = __uint128_t(res) * base + (randomized(elem) & mod);res = (x & mod) + (x >> 61);}__uint128_t x = __uint128_t(res) * base;res = (x & mod) + (x >> 61);if (res >= mod) res -= mod;return res >> (shift - 3);}template <typename D = Data,enable_if_t<is_same<D, Key>::value, nullptr_t> = nullptr>inline u32 hash(const D& dat) const {return inner_hash(dat);}template <typename D = Data,enable_if_t<is_same<decltype(D::first), Key>::value, nullptr_t> = nullptr>inline u32 hash(const D& dat) const {return inner_hash(dat.first);}template <typename D = Data,enable_if_t<is_same<D, Key>::value, nullptr_t> = nullptr>inline Key data_to_key(const D& dat) const {return dat;}template <typename D = Data,enable_if_t<is_same<decltype(D::first), Key>::value, nullptr_t> = nullptr>inline Key data_to_key(const D& dat) const {return dat.first;}void reallocate(u32 ncap) {vector<Data> ndata(ncap);vector<bool> nf(ncap);shift = 64 - __lg(ncap);for (u32 i = 0; i < cap; i++) {if (occupied_flag[i] && !deleted_flag[i]) {u32 h = hash(data[i]);while (nf[h]) h = (h + 1) & (ncap - 1);ndata[h] = move(data[i]);nf[h] = true;}}data.swap(ndata);occupied_flag.swap(nf);cap = ncap;occupied = s;deleted_flag.resize(cap);fill(std::begin(deleted_flag), std::end(deleted_flag), false);}inline bool extend_rate(u32 x) const { return x * 2 >= cap; }inline bool shrink_rate(u32 x) const {return HASHMAP_DEFAULT_SIZE < cap && x * 10 <= cap;}inline void extend() { reallocate(cap << 1); }inline void shrink() { reallocate(cap >> 1); }public:u32 cap, s, occupied;vector<Data> data;vector<bool> occupied_flag, deleted_flag;u32 shift;static u64 r;static constexpr uint32_t HASHMAP_DEFAULT_SIZE = 4;explicit HashMapBase(): cap(HASHMAP_DEFAULT_SIZE),s(0),occupied(0),data(cap),occupied_flag(cap),deleted_flag(cap),shift(64 - __lg(cap)) {}itr begin() const {u32 h = 0;while (h != cap) {if (occupied_flag[h] && !deleted_flag[h]) break;h++;}return itr(h, this);}itr end() const { return itr(this->cap, this); }friend itr begin(const HashMapBase& h) { return h.begin(); }friend itr end(const HashMapBase& h) { return h.end(); }itr find(const Key& key) const {u32 h = inner_hash(key);while (true) {if (occupied_flag[h] == false) return this->end();if (data_to_key(data[h]) == key) {if (deleted_flag[h] == true) return this->end();return itr(h, this);}h = (h + 1) & (cap - 1);}}bool contain(const Key& key) const { return find(key) != this->end(); }itr insert(const Data& d) {u32 h = hash(d);while (true) {if (occupied_flag[h] == false) {if (extend_rate(occupied + 1)) {extend();h = hash(d);continue;}data[h] = d;occupied_flag[h] = true;++occupied, ++s;return itr(h, this);}if (data_to_key(data[h]) == data_to_key(d)) {if (deleted_flag[h] == true) {data[h] = d;deleted_flag[h] = false;++s;}return itr(h, this);}h = (h + 1) & (cap - 1);}}// tips for speed up :// if return value is unnecessary, make argument_2 false.itr erase(itr it, bool get_next = true) {if (it == this->end()) return this->end();s--;if (!get_next) {this->deleted_flag[it.i] = true;if (shrink_rate(s)) shrink();return this->end();}itr nxt = it;nxt++;this->deleted_flag[it.i] = true;if (shrink_rate(s)) {Data d = data[nxt.i];shrink();it = find(data_to_key(d));}return nxt;}itr erase(const Key& key) { return erase(find(key)); }int count(const Key& key) { return find(key) == end() ? 0 : 1; }bool empty() const { return s == 0; }int size() const { return s; }void clear() {fill(std::begin(occupied_flag), std::end(occupied_flag), false);fill(std::begin(deleted_flag), std::end(deleted_flag), false);s = occupied = 0;}void reserve(int n) {if (n <= 0) return;n = 1 << min(23, __lg(n) + 2);if (cap < u32(n)) reallocate(n);}};template <typename Key, typename Data>uint64_t HashMapBase<Key, Data>::r =chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();} // namespace HashMapImpltemplate <typename Key, typename Val>struct HashMap : HashMapImpl::HashMapBase<Key, pair<Key, Val>> {using base = typename HashMapImpl::HashMapBase<Key, pair<Key, Val>>;using HashMapImpl::HashMapBase<Key, pair<Key, Val>>::HashMapBase;using Data = pair<Key, Val>;Val& operator[](const Key& k) {typename base::u32 h = base::inner_hash(k);while (true) {if (base::occupied_flag[h] == false) {if (base::extend_rate(base::occupied + 1)) {base::extend();h = base::hash(k);continue;}base::data[h].first = k;base::data[h].second = Val();base::occupied_flag[h] = true;++base::occupied, ++base::s;return base::data[h].second;}if (base::data[h].first == k) {if (base::deleted_flag[h] == true) {base::data[h].second = Val();base::deleted_flag[h] = false;++base::s;}return base::data[h].second;}h = (h + 1) & (base::cap - 1);}}typename base::itr emplace(const Key& key, const Val& val) {return base::insert(Data(key, val));}};ll x;void input(){in(x);}void solve(){HashMap<int, int> cnt;vector<vi> p(301);int ans = 0;rep(i, 301){rep(j, i, 301){rep(k, j, 301){int val = i * i * i + j * j * j + k * k * k;p[k].push_back(val);}}for(auto x : p[i]){cnt[x]++;}rep(j, i, 301){rep(k, j, 301){int val = i * i * i + j * j * j + k * k * k;ans += cnt[x - val];}}}out(ans);}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(20);input();solve();}