結果
| 問題 |
No.800 四平方定理
|
| コンテスト | |
| ユーザー |
 yukinon0808
|
| 提出日時 | 2019-03-18 00:06:18 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 18,210 bytes |
| コンパイル時間 | 1,242 ms |
| コンパイル使用メモリ | 156,748 KB |
| 最終ジャッジ日時 | 2024-11-14 21:20:35 |
| 合計ジャッジ時間 | 1,630 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:9:21: error: ‘operator<<’ function uses ‘auto’ type specifier without trailing return type
9 | template<typename T>auto&operator<<(ostream&s,const vector<T>&v){s<<"[";bool a=1;for(auto e:v){s<<(a?"":" ")<<e;a=0;}s<<"]";return s;}
| ^~~~
main.cpp:9:21: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:10:32: error: ‘operator<<’ function uses ‘auto’ type specifier without trailing return type
10 | template<typename T,typename U>auto&operator<<(ostream&s,const pair<T,U>&p){s<<"("<<p.first<<","<<p.second<<")";return s;}
| ^~~~
main.cpp:10:32: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:11:21: error: ‘operator<<’ function uses ‘auto’ type specifier without trailing return type
11 | template<typename T>auto&operator<<(ostream&s,const set<T>&st){s<<"{";bool a=1;for(auto e:st){s<<(a?"":" ")<<e;a=0;}s<<"}";return s;}
| ^~~~
main.cpp:11:21: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:12:32: error: ‘operator<<’ function uses ‘auto’ type specifier without trailing return type
12 | template<typename T,typename U>auto&operator<<(ostream&s,const map<T,U>&m){s<<"{";bool a=1;for(auto e:m){s<<(a?"":" ")<<e.first<<":"<<e.second;a=0;}s<<"}";return s;}
| ^~~~
main.cpp:12:32: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
ソースコード
#include <bits/stdc++.h>
#define int long long int
using namespace std;
template<typename T,typename U> using P=pair<T,U>;
template<typename T> using V=vector<T>;
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>auto&operator<<(ostream&s,const vector<T>&v){s<<"[";bool a=1;for(auto e:v){s<<(a?"":" ")<<e;a=0;}s<<"]";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const pair<T,U>&p){s<<"("<<p.first<<","<<p.second<<")";return s;}
template<typename T>auto&operator<<(ostream&s,const set<T>&st){s<<"{";bool a=1;for(auto e:st){s<<(a?"":" ")<<e;a=0;}s<<"}";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const map<T,U>&m){s<<"{";bool a=1;for(auto e:m){s<<(a?"":" ")<<e.first<<":"<<e.second;a=0;}s<<"}";return s;}
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl;
struct edge { int to, cost; };
const int INF = 1e18;
const int MOD = 1e9+7;
/// like std::equal_to but no need to #include <functional>
template<typename T>
struct HashMapEqualTo
{
constexpr bool operator()(const T& lhs, const T& rhs) const
{
return lhs == rhs;
}
};
/// A cache-friendly hash table with open addressing, linear probing and power-of-two capacity
template <typename KeyT, typename ValueT, typename HashT = std::hash<KeyT>, typename EqT = HashMapEqualTo<KeyT>>
class HashMap
{
private:
using MyType = HashMap<KeyT, ValueT, HashT, EqT>;
using PairT = std::pair<KeyT, ValueT>;
public:
using size_type = size_t;
using value_type = PairT;
using reference = PairT&;
using const_reference = const PairT&;
class iterator
{
public:
using iterator_category = std::forward_iterator_tag;
using difference_type = size_t;
using distance_type = size_t;
using value_type = std::pair<KeyT, ValueT>;
using pointer = value_type*;
using reference = value_type&;
iterator() { }
iterator(MyType* hash_map, size_t bucket) : _map(hash_map), _bucket(bucket)
{
}
iterator& operator++()
{
this->goto_next_element();
return *this;
}
iterator operator++(int)
{
size_t old_index = _bucket;
this->goto_next_element();
return iterator(_map, old_index);
}
reference operator*() const
{
return _map->_pairs[_bucket];
}
pointer operator->() const
{
return _map->_pairs + _bucket;
}
bool operator==(const iterator& rhs) const
{
// DCHECK_EQ_F(_map, rhs._map);
return this->_bucket == rhs._bucket;
}
bool operator!=(const iterator& rhs) const
{
// DCHECK_EQ_F(_map, rhs._map);
return this->_bucket != rhs._bucket;
}
private:
void goto_next_element()
{
// DCHECK_LT_F(_bucket, _map->_num_buckets);
do {
_bucket++;
} while (_bucket < _map->_num_buckets && _map->_states[_bucket] != State::FILLED);
}
//private:
// friend class MyType;
public:
MyType* _map;
size_t _bucket;
};
class const_iterator
{
public:
using iterator_category = std::forward_iterator_tag;
using difference_type = size_t;
using distance_type = size_t;
using value_type = const std::pair<KeyT, ValueT>;
using pointer = value_type*;
using reference = value_type&;
const_iterator() { }
const_iterator(iterator proto) : _map(proto._map), _bucket(proto._bucket)
{
}
const_iterator(const MyType* hash_map, size_t bucket) : _map(hash_map), _bucket(bucket)
{
}
const_iterator& operator++()
{
this->goto_next_element();
return *this;
}
const_iterator operator++(int)
{
size_t old_index = _bucket;
this->goto_next_element();
return const_iterator(_map, old_index);
}
reference operator*() const
{
return _map->_pairs[_bucket];
}
pointer operator->() const
{
return _map->_pairs + _bucket;
}
bool operator==(const const_iterator& rhs) const
{
// DCHECK_EQ_F(_map, rhs._map);
return this->_bucket == rhs._bucket;
}
bool operator!=(const const_iterator& rhs) const
{
// DCHECK_EQ_F(_map, rhs._map);
return this->_bucket != rhs._bucket;
}
private:
void goto_next_element()
{
// DCHECK_LT_F(_bucket, _map->_num_buckets);
do {
_bucket++;
} while (_bucket < _map->_num_buckets && _map->_states[_bucket] != State::FILLED);
}
//private:
// friend class MyType;
public:
const MyType* _map;
size_t _bucket;
};
// ------------------------------------------------------------------------
HashMap() = default;
HashMap(const HashMap& other)
{
reserve(other.size());
insert(other.cbegin(), other.cend());
}
HashMap(HashMap&& other)
{
*this = std::move(other);
}
HashMap& operator=(const HashMap& other)
{
clear();
reserve(other.size());
insert(other.cbegin(), other.cend());
return *this;
}
void operator=(HashMap&& other)
{
this->swap(other);
}
~HashMap()
{
for (size_t bucket=0; bucket<_num_buckets; ++bucket) {
if (_states[bucket] == State::FILLED) {
_pairs[bucket].~PairT();
}
}
free(_states);
free(_pairs);
}
void swap(HashMap& other)
{
std::swap(_hasher, other._hasher);
std::swap(_eq, other._eq);
std::swap(_states, other._states);
std::swap(_pairs, other._pairs);
std::swap(_num_buckets, other._num_buckets);
std::swap(_num_filled, other._num_filled);
std::swap(_max_probe_length, other._max_probe_length);
std::swap(_mask, other._mask);
}
// -------------------------------------------------------------
iterator begin()
{
size_t bucket = 0;
while (bucket<_num_buckets && _states[bucket] != State::FILLED) {
++bucket;
}
return iterator(this, bucket);
}
const_iterator cbegin() const
{
size_t bucket = 0;
while (bucket<_num_buckets && _states[bucket] != State::FILLED) {
++bucket;
}
return const_iterator(this, bucket);
}
const_iterator begin() const
{
return cbegin();
}
iterator end()
{
return iterator(this, _num_buckets);
}
const_iterator cend() const
{
return const_iterator(this, _num_buckets);
}
const_iterator end() const
{
return cend();
}
size_t size() const
{
return _num_filled;
}
bool empty() const
{
return _num_filled==0;
}
// Returns the number of buckets.
size_t bucket_count() const
{
return _num_buckets;
}
/// Returns average number of elements per bucket.
float load_factor() const
{
return static_cast<float>(_num_filled) / static_cast<float>(_num_buckets);
}
// ------------------------------------------------------------
template<typename KeyLike>
iterator find(const KeyLike& key)
{
auto bucket = this->find_filled_bucket(key);
if (bucket == (size_t)-1) {
return this->end();
}
return iterator(this, bucket);
}
template<typename KeyLike>
const_iterator find(const KeyLike& key) const
{
auto bucket = this->find_filled_bucket(key);
if (bucket == (size_t)-1)
{
return this->end();
}
return const_iterator(this, bucket);
}
template<typename KeyLike>
bool contains(const KeyLike& k) const
{
return find_filled_bucket(k) != (size_t)-1;
}
template<typename KeyLike>
size_t count(const KeyLike& k) const
{
return find_filled_bucket(k) != (size_t)-1 ? 1 : 0;
}
/// Returns the matching ValueT or nullptr if k isn't found.
template<typename KeyLike>
ValueT* try_get(const KeyLike& k)
{
auto bucket = find_filled_bucket(k);
if (bucket != (size_t)-1) {
return &_pairs[bucket].second;
} else {
return nullptr;
}
}
/// Const version of the above
template<typename KeyLike>
const ValueT* try_get(const KeyLike& k) const
{
auto bucket = find_filled_bucket(k);
if (bucket != (size_t)-1) {
return &_pairs[bucket].second;
} else {
return nullptr;
}
}
/// Convenience function.
template<typename KeyLike>
const ValueT get_or_return_default(const KeyLike& k) const
{
const ValueT* ret = try_get(k);
if (ret) {
return *ret;
} else {
return ValueT();
}
}
// -----------------------------------------------------
/// Returns a pair consisting of an iterator to the inserted element
/// (or to the element that prevented the insertion)
/// and a bool denoting whether the insertion took place.
std::pair<iterator, bool> insert(const KeyT& key, const ValueT& value)
{
check_expand_need();
auto bucket = find_or_allocate(key);
if (_states[bucket] == State::FILLED) {
return { iterator(this, bucket), false };
} else {
_states[bucket] = State::FILLED;
new(_pairs + bucket) PairT(key, value);
_num_filled++;
return { iterator(this, bucket), true };
}
}
std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT>& p)
{
return insert(p.first, p.second);
}
void insert(const_iterator begin, const_iterator end)
{
// TODO: reserve space exactly once.
for (; begin != end; ++begin) {
insert(begin->first, begin->second);
}
}
/// Same as above, but contains(key) MUST be false
void insert_unique(KeyT&& key, ValueT&& value)
{
// DCHECK_F(!contains(key));
check_expand_need();
auto bucket = find_empty_bucket(key);
_states[bucket] = State::FILLED;
new(_pairs + bucket) PairT(std::move(key), std::move(value));
_num_filled++;
}
void insert_unique(std::pair<KeyT, ValueT>&& p)
{
insert_unique(std::move(p.first), std::move(p.second));
}
void insert_or_assign(const KeyT& key, ValueT&& value)
{
check_expand_need();
auto bucket = find_or_allocate(key);
// Check if inserting a new value rather than overwriting an old entry
if (_states[bucket] == State::FILLED) {
_pairs[bucket].second = value;
} else {
_states[bucket] = State::FILLED;
new(_pairs + bucket) PairT(key, value);
_num_filled++;
}
}
/// Return the old value or ValueT() if it didn't exist.
ValueT set_get(const KeyT& key, const ValueT& new_value)
{
check_expand_need();
auto bucket = find_or_allocate(key);
// Check if inserting a new value rather than overwriting an old entry
if (_states[bucket] == State::FILLED) {
ValueT old_value = _pairs[bucket].second;
_pairs[bucket] = new_value.second;
return old_value;
} else {
_states[bucket] = State::FILLED;
new(_pairs + bucket) PairT(key, new_value);
_num_filled++;
return ValueT();
}
}
/// Like std::map<KeyT,ValueT>::operator[].
ValueT& operator[](const KeyT& key)
{
check_expand_need();
auto bucket = find_or_allocate(key);
/* Check if inserting a new value rather than overwriting an old entry */
if (_states[bucket] != State::FILLED) {
_states[bucket] = State::FILLED;
new(_pairs + bucket) PairT(key, ValueT());
_num_filled++;
}
return _pairs[bucket].second;
}
// -------------------------------------------------------
/// Erase an element from the hash table.
/// return false if element was not found
bool erase(const KeyT& key)
{
auto bucket = find_filled_bucket(key);
if (bucket != (size_t)-1) {
_states[bucket] = State::ACTIVE;
_pairs[bucket].~PairT();
_num_filled -= 1;
return true;
} else {
return false;
}
}
/// Erase an element using an iterator.
/// Returns an iterator to the next element (or end()).
iterator erase(iterator it)
{
// DCHECK_EQ_F(it._map, this);
// DCHECK_LT_F(it._bucket, _num_buckets);
_states[it._bucket] = State::ACTIVE;
_pairs[it._bucket].~PairT();
_num_filled -= 1;
return ++it;
}
/// Remove all elements, keeping full capacity.
void clear()
{
for (size_t bucket=0; bucket<_num_buckets; ++bucket) {
if (_states[bucket] == State::FILLED) {
_states[bucket] = State::INACTIVE;
_pairs[bucket].~PairT();
}
}
_num_filled = 0;
_max_probe_length = -1;
}
/// Make room for this many elements
void reserve(size_t num_elems)
{
size_t required_buckets = num_elems + num_elems/2 + 1;
if (required_buckets <= _num_buckets) {
return;
}
size_t num_buckets = 4;
while (num_buckets < required_buckets) { num_buckets *= 2; }
auto new_states = (State*)malloc(num_buckets * sizeof(State));
auto new_pairs = (PairT*)malloc(num_buckets * sizeof(PairT));
if (!new_states || !new_pairs) {
free(new_states);
free(new_pairs);
throw std::bad_alloc();
}
//auto old_num_filled = _num_filled;
auto old_num_buckets = _num_buckets;
auto old_states = _states;
auto old_pairs = _pairs;
_num_filled = 0;
_num_buckets = num_buckets;
_mask = _num_buckets - 1;
_states = new_states;
_pairs = new_pairs;
std::fill_n(_states, num_buckets, State::INACTIVE);
_max_probe_length = -1;
for (size_t src_bucket=0; src_bucket<old_num_buckets; src_bucket++) {
if (old_states[src_bucket] == State::FILLED) {
auto& src_pair = old_pairs[src_bucket];
auto dst_bucket = find_empty_bucket(src_pair.first);
// DCHECK_NE_F(dst_bucket, (size_t)-1);
// DCHECK_NE_F(_states[dst_bucket], State::FILLED);
_states[dst_bucket] = State::FILLED;
new(_pairs + dst_bucket) PairT(std::move(src_pair));
_num_filled += 1;
src_pair.~PairT();
}
}
//DCHECK_EQ_F(old_num_filled, _num_filled);
free(old_states);
free(old_pairs);
}
private:
// Can we fit another element?
void check_expand_need()
{
reserve(_num_filled + 1);
}
// Find the bucket with this key, or return (size_t)-1
template<typename KeyLike>
size_t find_filled_bucket(const KeyLike& key) const
{
if (empty()) { return (size_t)-1; } // Optimization
auto hash_value = _hasher(key);
for (int offset=0; offset<=_max_probe_length; ++offset) {
auto bucket = (hash_value + offset) & _mask;
if (_states[bucket] == State::FILLED) {
if (_eq(_pairs[bucket].first, key)) {
return bucket;
}
} else if (_states[bucket] == State::INACTIVE) {
return (size_t)-1; // End of the chain!
}
}
return (size_t)-1;
}
// Find the bucket with this key, or return a good empty bucket to place the key in.
// In the latter case, the bucket is expected to be filled.
size_t find_or_allocate(const KeyT& key)
{
auto hash_value = _hasher(key);
size_t hole = (size_t)-1;
int offset=0;
for (; offset<=_max_probe_length; ++offset) {
auto bucket = (hash_value + offset) & _mask;
if (_states[bucket] == State::FILLED) {
if (_eq(_pairs[bucket].first, key)) {
return bucket;
}
} else if (_states[bucket] == State::INACTIVE) {
return bucket;
} else {
// ACTIVE: keep searching
if (hole == (size_t)-1) {
hole = bucket;
}
}
}
// No key found - but maybe a hole for it
// DCHECK_EQ_F(offset, _max_probe_length+1);
if (hole != (size_t)-1) {
return hole;
}
// No hole found within _max_probe_length
for (; ; ++offset) {
auto bucket = (hash_value + offset) & _mask;
if (_states[bucket] != State::FILLED) {
_max_probe_length = offset;
return bucket;
}
}
}
// key is not in this map. Find a place to put it.
size_t find_empty_bucket(const KeyT& key)
{
auto hash_value = _hasher(key);
for (int offset=0; ; ++offset) {
auto bucket = (hash_value + offset) & _mask;
if (_states[bucket] != State::FILLED) {
if (offset > _max_probe_length) {
_max_probe_length = offset;
}
return bucket;
}
}
}
private:
enum class State : uint8_t
{
INACTIVE, // Never been touched
ACTIVE, // Is inside a search-chain, but is empty
FILLED // Is set with key/value
};
HashT _hasher;
EqT _eq;
State* _states = nullptr;
PairT* _pairs = nullptr;
size_t _num_buckets = 0;
size_t _num_filled = 0;
int _max_probe_length = -1; // Our longest bucket-brigade is this long. ONLY when we have zero elements is this ever negative (-1).
size_t _mask = 0; // _num_buckets minus one
};
signed main() {
int N, D; cin >> N >> D;
HashMap<int,int> cnt;
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
cnt[x*x + y*y]++;
}
}
int ans = 0;
for (int z = 1; z <= N; z++) {
for (int w = 1; w <= N; w++) {
ans += cnt[w*w - z*z + D];
}
}
cout << ans << endl;
return 0;
}