結果
| 問題 |
No.8016 unordered_mapなるたけ落とすマン
|
| ユーザー |
 tonegawa
|
| 提出日時 | 2020-11-24 22:56:04 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 60 ms / 1,000 ms |
| コード長 | 5,967 bytes |
| コンパイル時間 | 1,430 ms |
| コンパイル使用メモリ | 131,132 KB |
| 最終ジャッジ日時 | 2025-01-16 05:31:46 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 48 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:239:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
239 | ll n, m;scanf("%lld %lld", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
main.cpp:242:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
242 | ll a;scanf("%lld", &a);
| ~~~~~^~~~~~~~~~~~
main.cpp:246:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
246 | ll a;scanf("%lld", &a);
| ~~~~~^~~~~~~~~~~~
ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#include <numeric>
#include <random>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;
template<typename Key>
struct hashset{
private:
float load_factor = 0.8;
int table_size = 16;
int mod = 15;
Key null_key;
uint32_t mask;
vector<Key> table;
vector<Key> data;
function<uint32_t(Key)> f = std::hash<uint32_t>();
void expand_table(){
table_size *= 2;
mod = table_size - 1;
table.resize(table_size);
fill(table.begin(), table.end(), null_key);
for(auto v:data) inner_insert(v);
}
void inner_insert(Key k){
uint32_t h = f(k^mask) & mod;
while(true){
if(table[h]!=null_key){
if(table[h]==k) return;
h = (h + 1) & mod;
}else{
table[h] = k;
if(float(data.size())>load_factor*float(table_size)){
expand_table();
}
return;
}
}
}
public:
hashset():
null_key(std::numeric_limits<Key>::max()),mask(random_device()()),
table(table_size, null_key){}
int size(){
return data.size();
}
void insert(Key k){
assert(k!=null_key);
uint32_t h = f(k^mask) & mod;
while(true){
if(table[h]!=null_key){
if(table[h]==k) return;
h = (h + 1) & mod;
}else{
data.push_back(k);
table[h] = k;
if(float(data.size())>load_factor*float(table_size)){
expand_table();
}
return;
}
}
}
bool contain(Key k){
uint32_t h = f(k^mask) & mod;
while(true){
if(table[h]==null_key) return false;
if(table[h]==k) return true;
h = (h + 1) & mod;
}
}
};
template<typename Key, typename Val>
struct hashmap{
float load_factor = 0.8;
int table_size = 16;
int mod = 15;
Key null_key;
uint32_t mask;
vector<Key> key_table;
vector<Val> val_table;
vector<pair<Key, Val>> data;
function<uint32_t(Key)> f = std::hash<uint32_t>();
hashmap():
null_key(std::numeric_limits<Key>::max()), mask(random_device()()),
key_table(table_size, null_key), val_table(table_size){}
int size(){
return data.size();
}
void expand_table(){
table_size *= 2;
mod = table_size - 1;
key_table.resize(table_size);
val_table.resize(table_size);
fill(key_table.begin(), key_table.end(), null_key);
for(auto d:data) emplace(d.first, d.second, false);
}
void emplace(Key k, Val v, bool g=true){
assert(k!=null_key);
uint32_t h = (f(k)^mask) & mod;
while(true){
if(key_table[h]!=null_key){
if(key_table[h]==k) return;
h = (h + 1) & mod;
}else{
if(g) data.push_back({k, v});
key_table[h] = k;
val_table[h] = v;
if(float(data.size())>load_factor*float(table_size)){
expand_table();
}
return;
}
}
}
bool contain(Key k){
assert(k!=null_key);
uint32_t h = (f(k)^mask) & mod;
while(true){
if(key_table[h]==null_key) return false;
if(key_table[h]==k) return true;
h = (h + 1) & mod;
}
}
Val at(Key k){
assert(k!=null_key);
uint32_t h = (f(k)^mask) & mod;
while(true){
assert(key_table[h]!=null_key);
if(key_table[h]==k) return val_table[h];
h = (h + 1) & mod;
}
}
};
template<typename Key>
struct hashmultiset{
private:
float load_factor = 0.8;
int table_size = 16;
int mod = 15;
Key null_key;
uint32_t mask;
vector<Key> key_table;
vector<int> idx_table;
vector<pair<Key, int>> data;
function<uint32_t(Key)> f = std::hash<uint32_t>();
void expand_table(){
table_size *= 2;
mod = table_size - 1;
key_table.resize(table_size);
idx_table.resize(table_size);
fill(key_table.begin(), key_table.end(), null_key);
for(int i=0;i<data.size();i++) inner_insert(data[i].first, i);
}
void inner_insert(Key k, int idx){
uint32_t h = f(k^mask) & mod;
while(true){
if(key_table[h]!=null_key){
if(key_table[h]==k) return;
h = (h + 1) & mod;
}else{
key_table[h] = k;
idx_table[h]= idx;
if(float(data.size())>load_factor*float(table_size)){
expand_table();
}
return;
}
}
}
public:
hashmultiset():
null_key(std::numeric_limits<Key>::max()), mask(random_device()()),
key_table(table_size, null_key), idx_table(table_size){}
int size(){
return data.size();
}
void insert(Key k){
assert(k!=null_key);
uint32_t h = f(k^mask) & mod;
while(true){
if(key_table[h]!=null_key){
if(key_table[h]==k){
data[idx_table[h]].second++;
return;
}
h = (h + 1) & mod;
}else{
int idx = data.size();
data.push_back({k, 1});
key_table[h] = k;
idx_table[h] = idx;
if(float(data.size())>load_factor*float(table_size)){
expand_table();
}
return;
}
}
}
int count(Key k){
assert(k!=null_key);
uint32_t h = f(k^mask) & mod;
while(true){
if(key_table[h]==null_key) return 0;
if(key_table[h]==k) return data[idx_table[h]].second;
h = (h + 1) & mod;
}
}
};
int main(){
ll n, m;scanf("%lld %lld", &n, &m);
hashmultiset<ll> st;
for(int i=0;i<n;i++){
ll a;scanf("%lld", &a);
st.insert(a);
}
for(int i=0;i<m;i++){
ll a;scanf("%lld", &a);
if(i==m-1) printf("%d\n", st.count(a));
else printf("%d ", st.count(a));
}
}