Submission #1186389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186389		Tymond	Seats (IOI18_seats)	C++20	Compilation error	0 ms	0 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const int INF = 1e9;
const int MAXN =  1e6 + 7;
const int B = 1e3;
vector<pii> pos;
vector<vi> A;
int h, w, ans;
pii cnt[MAXN];//.fi - ile trójek z dużymi elementami, .se - ile trójek z małymi elementami
pii changeB[MAXN / B + 10];
unordered_map<pii, int, custom_hash> cntB[MAXN / B + 10];
const pii correct = mp(4, 0);

void operator+=(pii& a, const pii& b){
    a.fi += b.fi;
    a.se += b.se;
}

pii operator+(const pii& a, const pii& b){
    return mp(a.fi + b.fi, a.se + b.se);
}

pii operator-(const pii& a, const pii& b){
    return mp(a.fi - b.fi, a.se - b.se);
}

int isOk(int x){
    if(cnt[x] + changeB[x / B] == correct){
        return 1;
    }
    return 0;
}

int cntOk(int b){
    if(cntB[b].find(correct - changeB[b]) == cntB[b].end()){
        return 0;
    }
    return cntB[b][correct - changeB[b]];
}

void upd(int l, int p, pii x){
    p = min(p, h * w);
    if(l > p){
        return;
    }
    
    //cerr << l << ' ' << p << ' ' << x.fi << ' ' << x.se << '\n';
   while(l <= p && l % B != 0){
        ans -= isOk(l);
        cnt[l] += x;
        ans += isOk(l);
        l++;
    }
    //cerr << l << ' ' << ans << '\n';
   // cerr << l << ' ' << p << ' ' << x.fi << ' ' << x.se << '\n';
    while(l + B - 1 <= p){
       // cerr << l << '\n';
        ans -= cntOk(l / B);
        changeB[l / B] += x;
       /// cerr << l << '\n';
        ans += cntOk(l / B);
        l += B;
       // cerr << l << '\n';
    }
   // cerr << l << ' ' << ans << '\n';
   // cerr << l << ' ' << p << ' ' << x.fi << ' ' << x.se << '\n';
   //cerr << cnt[2] + changeB[2 / B] << '\n';
    while(l <= p){
        ans -= isOk(l);
        cnt[l] += x;
        ans += isOk(l);
        l++;
    }
   // cerr << l << ' ' << ans << '\n';
}

void change(int x, int y, int val=1){
   // cerr << "NIGGA1\n";
    vi curr = {A[x][y], A[x + 1][y], A[x][y + 1], A[x + 1][y + 1]};
    sort(all(curr));
   // cerr << "NIGGA2\n";
    upd(curr[0], curr[1] - 1, mp(val, 0));
    //cerr << "NIGGA3\n";
    upd(curr[2], curr[3] - 1, mp(0, val));
    //cerr << "NIGGA3\n";
}

void give_initial_chart(int H, int W, vi R, vi C){
    h = H;
    w = W;
    pos.resize(h * w + 1);
    A.resize(h + 2, vi(w + 2, INF));
    for(int i = 1; i <= h * w; i++){
        pos[i] = mp(R[i - 1] + 1, C[i - 1] + 1);
        A[R[i - 1] + 1][C[i - 1] + 1] = i;
    }
   // cerr << "NIGGA\n";
    for(int i = 0; i <= h; i++){
        for(int j = 0; j <= w; j++){
            change(i, j);
        }
    }
    //cerr << "NIGGA\n";
    ans = 0;
    for(int i = 1; i <= h * w; i++){
        cnt[i] += changeB[i / B];
        if(cnt[i] == correct){
            ans++;
        }
        cntB[i / B][cnt[i]]++;
        //cerr << i / B << ' ' << cnt[i] << '\n';
    }
    
    for(int i = 0; i <= h * w; i++){
        changeB[i / B] = mp(0, 0);
    }
    //cerr << ans << '\n';
   //cerr << "NIGGA\n";
}

//zamień miejsca liczb a i b
//potem zwróć wynik po zamianie
int swap_seats(int a, int b) {
    a++;
    b++;
    int p[2] = {a, b};
    //cerr << pos[a] << ' ' << pos[b] << '\n';
    for(int j = 0; j < 2; j++){
        for(int x = pos[p[j]].fi - 1; x <= pos[p[j]].fi; x++){
            for(int y = pos[p[j]].se - 1; y <= pos[p[j]].se; y++){
                change(x, y, -1);
            }
        }
    }
    //cerr << "NIGGA\n";
    swap(pos[p[0]], pos[p[1]]);
    swap(A[pos[p[0]].fi][pos[p[0]].se], A[pos[p[1]].fi][pos[p[1]].se]);
    for(int j = 0; j < 2; j++){
        for(int x = pos[p[j]].fi - 1; x <= pos[p[j]].fi; x++){
            for(int y = pos[p[j]].se - 1; y <= pos[p[j]].se; y++){
                change(x, y);
            }
        }
    }
    ans = 0;
    for(int i = 1; i <= h * w; i++){
        if(cnt[i] + changeB[i / B] == correct){
            ans++;
        }
    }
    //cerr << "NIGGA\n";
    return ans;
}

/*int main(){
    give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1, 1, 2, 2});
    
    cout << swap_seats(0, 5) << '\n';
    cout << swap_seats(0, 5) << '\n';

    return 0;
}*/

Compilation message (stderr)

In file included from /usr/include/c++/11/bits/hashtable.h:35,
                 from /usr/include/c++/11/unordered_map:46,
                 from /usr/include/c++/11/functional:61,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from seats.cpp:1:
/usr/include/c++/11/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code(const _Key&) const [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _Hash = custom_hash; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true; std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code = long unsigned int]':
/usr/include/c++/11/bits/hashtable.h:1593:46:   required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::find(const key_type&) [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = custom_hash; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::iterator = std::__detail::_Insert_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::allocator<std::pair<const std::pair<int, int>, int> >, std::__detail::_Select1st, std::equal_to<std::pair<int, int> >, custom_hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::iterator; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::key_type = std::pair<int, int>]'
/usr/include/c++/11/bits/unordered_map.h:869:25:   required from 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::find(const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Hash = custom_hash; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator = std::__detail::_Insert_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::allocator<std::pair<const std::pair<int, int>, int> >, std::__detail::_Select1st, std::equal_to<std::pair<int, int> >, custom_hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::iterator; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::key_type = std::pair<int, int>]'
seats.cpp:81:20:   required from here
/usr/include/c++/11/bits/hashtable_policy.h:1217:23: error: static assertion failed: hash function must be invocable with an argument of key type
 1217 |         static_assert(__is_invocable<const _Hash&, const _Key&>{},
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/hashtable_policy.h:1217:23: note: 'std::__is_invocable<const custom_hash&, const std::pair<int, int>&>{}' evaluates to false
/usr/include/c++/11/bits/hashtable_policy.h:1219:25: error: no match for call to '(const custom_hash) (const std::pair<int, int>&)'
 1219 |         return _M_hash()(__k);
      |                ~~~~~~~~~^~~~~
seats.cpp:37:12: note: candidate: 'size_t custom_hash::operator()(uint64_t) const'
   37 |     size_t operator()(uint64_t x) const {
      |            ^~~~~~~~
seats.cpp:37:32: note:   no known conversion for argument 1 from 'const std::pair<int, int>' to 'uint64_t' {aka 'long unsigned int'}
   37 |     size_t operator()(uint64_t x) const {
      |                       ~~~~~~~~~^