Submission #511830

#	Time	Username	Problem	Language	Result	Execution time	Memory
511830		blue	Matching (CEOI11_mat)	C++17	Compilation error	0 ms	0 KiB

mat

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cassert>
using namespace std;

using vi = vector<int>;
using ll = long long;
#define sz(x) int(x.size())

const ll mod = 1'000'000'007;
const int bs = 1'000'007;

int mul(ll a, ll b)
{
    return (a*b) % mod;
}

int ad(ll a, ll b)
{
    return (a+b)%mod;
}

int pow(int b, int e)
{
    int res = 1;

    while(e > 0)
    {
        if(e & 1)
        {
            res = mul(res, b);
            e ^= 1;
        }
        else
        {
            b = mul(b, b);
            e >>= 1;
        }
    }

    return res;
}

int inv(int a)
{
    return pow(a, mod-2);
}


int n, m;
vi ct_bit, pow_bit;

int pow_bit_sum = 0;

void add(vi& bit, int i, int v)
{
    for(int j = i; j <= (1<<20); j += j&-j)
        bit[j] = (bit[j]+v)%mod;
}

int prefsum(vi& bit, int i)
{
    int res = 0;
    for(int j = i; j >= 1; j ^= j&-j)
        res = (res+bit[j])%mod;
    return res;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    vi s(1+n);
    for(int i = 1; i <= n; i++) cin >> s[i];




    vi h(1+m);
    map<int, int> hmap;

    for(int j = 1; j <= m; j++)
    {
        cin >> h[j];
        hmap[h[j]] = 0;
    }

    int hct = 0;
    for(auto& x: hmap) x.second = ++hct;
    for(int j = 1; j <= m; j++) h[j] = hmap[h[j]];

    hmap.clear();

    // for(int j = 1; j <= m; j++) cout << h[j] << ' ';
    // cout << '\n';
    // cerr << "check\n";

    // for(int q = 0; q < 20; q++) cerr << pow(2, q) << ' ' << pow(3, q) << '\n';

    int powbs[1+m];
    powbs[0] = 1;
    for(int e = 1; e <= m; e++) powbs[e] = mul(powbs[e-1], bs);

    int invbs[1+m];
    invbs[0] = 1;
    invbs[1] = inv(bs);
    for(int e = 2; e <= m; e++) invbs[e] = mul(invbs[e-1], invbs[1]);





    vi s_bit(1+n, 0);
    vi s_rank(1+n, 0);

    for(int i = 1; i <= n; i++)
    {
        for(int j = s[i]; j <= n; j += j&-j)
            s_bit[j]++;

        for(int j = s[i]-1; j >= 1; j -= j&-j)
            s_rank[s[i]] += s_bit[j];
    }

    int s_hash = 0;
    for(int i = 1; i <= n; i++) s_hash = ad(s_hash, mul(s_rank[i], powbs[n-i]));

    s_bit.clear();
    s_rank.clear();

    // cerr << "permutation ranks: ";
    // for(int i = 1; i <= n; i++) cerr << s_rank[i] << ' ';
    // cerr <<'\n';


    vi final_ans;

    // vi ct_bit(1+m, 0);
    // vi pow_bit(1+m, 0);
    ct_bit = pow_bit = vi((1<<20)+1, 0);

    int curr_hash = 0;

    for(int i = 1; i <= n; i++)
    {
        add(ct_bit, h[i], +1);

        add(pow_bit, h[i], powbs[m-i]);
        pow_bit_sum = ad(pow_bit_sum, powbs[m-i]);

        int curr_rank = 0;
        curr_rank += prefsum(ct_bit, h[i]-1);

        curr_hash = ad(curr_hash, mul(curr_rank, powbs[n-i]));
    }

    if(curr_hash == s_hash)
        final_ans.push_back(1);

    // cerr << "initial hash = " << curr_hash << '\n';



    for(int v = 2; v <= m-n+1; v++)
    {
        curr_hash = mul(curr_hash, bs);

        // add(ct_bit, h[v-1], -1);
        // add(ct_bit, h[v+n-1], +1);
        for(int j = h[v-1]; j <= m; j += j&-j)
            ct_bit[j]--;
        for(int j = h[v+n-1]; j <= m; j += j&-j)
            ct_bit[j]++;


        int nxt_rank = 0;

        // nxt_rank = ad(nxt_rank, prefsum(ct_bit, h[v+n-1]-1));
        for(int j = h[v+n-1]-1; j >= 1; j -= j&-j)
            nxt_rank = (nxt_rank + ct_bit) % mod;

        // curr_hash = ad(curr_hash, nxt_rank);
        curr_hash = (curr_hash + nxt_rank) % mod;



        int disc = 0;
        // disc = ad(disc, prefsum(pow_bit, m));
        disc = pow_bit_sum;
        // disc = ad(disc, mod - prefsum(pow_bit, h[v-1]));
        for(int j = h[v-1]; j >= 1; j -= j&-j)
            disc = (disc + mod - pow_bit[j]) % mod;

        int shft = v+n-2 - m + 1; //already shifted
        assert(shft <= 0);

        disc = mul(disc, invbs[-shft]);

        curr_hash = ad(curr_hash, mod - disc);

        add(pow_bit, h[v-1], mod - powbs[m - (v-1)]);
        add(pow_bit, h[v+n-1], powbs[m - (v+n-1)]);

        pow_bit_sum = ad(pow_bit_sum, mod - powbs[m - (v-1)]);
        pow_bit_sum = ad(pow_bit_sum, powbs[m - (v+n-1)]);

        if(curr_hash == s_hash)
            final_ans.push_back(v);
    }

    cout << sz(final_ans) << '\n';
    for(int v: final_ans) cout << v << ' ';
    cout << '\n';
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:186:34: error: no match for 'operator+' (operand types are 'int' and 'vi' {aka 'std::vector<int>'})
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                         ~~~~~~~~ ^ ~~~~~~
      |                         |          |
      |                         int        vi {aka std::vector<int>}
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:508:5: note: candidate: 'template<class _Iterator> constexpr std::reverse_iterator<_Iterator> std::operator+(typename std::reverse_iterator<_Iterator>::difference_type, const std::reverse_iterator<_Iterator>&)'
  508 |     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:508:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   'vi' {aka 'std::vector<int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1540:5: note: candidate: 'template<class _Iterator> constexpr std::move_iterator<_IteratorL> std::operator+(typename std::move_iterator<_IteratorL>::difference_type, const std::move_iterator<_IteratorL>&)'
 1540 |     operator+(typename move_iterator<_Iterator>::difference_type __n,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1540:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   'vi' {aka 'std::vector<int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6022:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6022 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6022:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:56,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.tcc:1160:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 1160 |     operator+(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.tcc:1160:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'const _CharT*' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:56,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.tcc:1180:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 1180 |     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.tcc:1180:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   'vi' {aka 'std::vector<int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6059:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
 6059 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6059:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6075:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, _CharT)'
 6075 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6075:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6087:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6087 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6087:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6093:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6093 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6093:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6099:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6099 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6099:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6121:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6121 |     operator+(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6121:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'const _CharT*' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6127:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6127 |     operator+(_CharT __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6127:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   'vi' {aka 'std::vector<int>'} is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6133:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const _CharT*)'
 6133 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6133:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6139:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, _CharT)'
 6139 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6139:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mat.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1185:5: note: candidate: 'template<class _Iterator, class _Container> __gnu_cxx::__normal_iterator<_Iterator, _Container> __gnu_cxx::operator+(typename __gnu_cxx::__normal_iterator<_Iterator, _Container>::difference_type, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
 1185 |     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1185:5: note:   template argument deduction/substitution failed:
mat.cpp:186:36: note:   'vi' {aka 'std::vector<int>'} is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
  186 |             nxt_rank = (nxt_rank + ct_bit) % mod;
      |                                    ^~~~~~