| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 879298 | serifefedartar | Matching (CEOI11_mat) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e6 + 100;
struct Node {
ll hash;
int cnt;
Node() : hash(0), cnt(0) { }
};
const ll P = 3412113;
vector<int> A, B, cc;
Node sg[4 * MAXN];
ll powP[MAXN];
Node merge(Node a, Node b) {
Node new_node;
new_node.cnt = a.cnt + b.cnt;
new_node.hash = (a.hash * powP[b.cnt] + b.hash) % MOD;
return new_node;
}
void update(int k, int a, int b, int pos, int val) {
if (b < pos || a > pos)
return ;
if (a == b) {
sg[k].hash = val;
sg[k].cnt = (val != 0);
return ;
}
update(2*k, a, (a+b)/2, pos, val);
update(2*k+1, (a+b)/2+1, b, pos, val);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
int main() {
fast
powP[0] = 1;
for (int i = 1; i < MAXN; i++)
powP[i] = (powP[i-1] * P) % MOD;
int N, M;
cin >> N >> M;
A = vector<int>(N + 1);
B = vector<int>(M + 1);
for (int i = 1; i <= N; i++)
cin << A[i];
ll main_hash = 0;
for (int i = 1; i <= N; i++)
main_hash = (main_hash * P + A[i]) % MOD;
for (int i = 1; i <= M; i++) {
cin >> B[i];
cc.push_back(B[i]);
}
sort(cc.begin(), cc.end());
for (int i = 1; i <= M; i++)
B[i] = upper_bound(cc.begin(), cc.end(), B[i]) - cc.begin();
ll sum = 0;
for (int i = 0; i < N; i++)
sum = (sum + powP[i]) % MOD;
for (int i = 1; i < N; i++)
update(1, 1, M, B[i], i);
vector<int> ans;
for (int i = N; i <= M; i++) {
update(1, 1, M, B[i], i);
ll hash_here = (sg[1].hash - (i - N) * sum % MOD + MOD) % MOD;
if (hash_here == main_hash)
ans.push_back(i - N + 1);
update(1, 1, M, B[i-N+1], 0);
}
cout << ans.size() << "\n";
for (auto u : ans)
cout << u << " ";
cout << "\n";
}
Compilation message (stderr)
mat.cpp: In function 'int main()':
mat.cpp:53:7: error: no match for 'operator<<' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
53 | cin << A[i];
mat.cpp:53:7: note: candidate: 'operator<<(int, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int})' (built-in)
mat.cpp:53:7: note: no known conversion for argument 1 from 'std::istream' {aka 'std::basic_istream<char>'} to 'int'
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from mat.cpp:1:
/usr/include/c++/10/bits/regex.h:1647:5: note: candidate: 'template<class _Ch_type, class _Ch_traits, class _Bi_iter> std::basic_ostream<_CharT, _Traits>& std::__cxx11::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::__cxx11::sub_match<_Bi_iter>&)'
1647 | operator<<(basic_ostream<_Ch_type, _Ch_traits>& __os,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1647:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:45,
from mat.cpp:1:
/usr/include/c++/10/cstddef:125:5: note: candidate: 'template<class _IntegerType> constexpr std::__byte_op_t<_IntegerType> std::operator<<(std::byte, _IntegerType)'
125 | operator<<(byte __b, _IntegerType __shift) noexcept
| ^~~~~~~~
/usr/include/c++/10/cstddef:125:5: note: template argument deduction/substitution failed:
mat.cpp:53:3: note: cannot convert 'std::cin' (type 'std::istream' {aka 'std::basic_istream<char>'}) to type 'std::byte'
53 | cin << A[i];
| ^~~
In file included from /usr/include/c++/10/bits/basic_string.h:48,
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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/string_view:622:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, std::basic_string_view<_CharT, _Traits>)'
622 | operator<<(basic_ostream<_CharT, _Traits>& __os,
| ^~~~~~~~
/usr/include/c++/10/string_view:622:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
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/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6458:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6458 | operator<<(basic_ostream<_CharT, _Traits>& __os,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6458:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/bits/ios_base.h:46,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/system_error:262:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::error_code&)'
262 | operator<<(basic_ostream<_CharT, _Traits>& __os, const error_code& __e)
| ^~~~~~~~
/usr/include/c++/10/system_error:262:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:506:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, _CharT)'
506 | operator<<(basic_ostream<_CharT, _Traits>& __out, _CharT __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:506:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:511:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, char)'
511 | operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:511:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:517:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char)'
517 | operator<<(basic_ostream<char, _Traits>& __out, char __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:517:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<char, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:523:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, signed char)'
523 | operator<<(basic_ostream<char, _Traits>& __out, signed char __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:523:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<char, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:528:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, unsigned char)'
528 | operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:528:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<char, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:589:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const _CharT*)'
589 | operator<<(basic_ostream<_CharT, _Traits>& __out, const _CharT* __s)
| ^~~~~~~~
/usr/include/c++/10/ostream:589:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/ostream:784,
from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/bits/ostream.tcc:321:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const char*)'
321 | operator<<(basic_ostream<_CharT, _Traits>& __out, const char* __s)
| ^~~~~~~~
/usr/include/c++/10/bits/ostream.tcc:321:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:606:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, const char*)'
606 | operator<<(basic_ostream<char, _Traits>& __out, const char* __s)
| ^~~~~~~~
/usr/include/c++/10/ostream:606:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<char, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:619:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, const signed char*)'
619 | operator<<(basic_ostream<char, _Traits>& __out, const signed char* __s)
| ^~~~~~~~
/usr/include/c++/10/ostream:619:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<char, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:624:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, const unsigned char*)'
624 | operator<<(basic_ostream<char, _Traits>& __out, const unsigned char* __s)
| ^~~~~~~~
/usr/include/c++/10/ostream:624:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<char, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/c++/10/istream:39,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/ostream:773:5: note: candidate: 'template<class _Ostream, class _Tp> typename std::enable_if<std::__and_<std::__not_<std::is_lvalue_reference<_Tp> >, std::__is_convertible_to_basic_ostream<_Ostream>, std::__is_insertable<typename std::__is_convertible_to_basic_ostream<_Tp>::__ostream_type, const _Tp&, void> >::value, typename std::__is_convertible_to_basic_ostream<_Tp>::__ostream_type>::type std::operator<<(_Ostream&&, const _Tp&)'
773 | operator<<(_Ostream&& __os, const _Tp& __x)
| ^~~~~~~~
/usr/include/c++/10/ostream:773:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/ostream: In substitution of 'template<class _Ostream, class _Tp> typename std::enable_if<std::__and_<std::__not_<std::is_lvalue_reference<_Tp> >, std::__is_convertible_to_basic_ostream<_Ostream>, std::__is_insertable<typename std::__is_convertible_to_basic_ostream<_Tp>::__ostream_type, const _Tp&, void> >::value, typename std::__is_convertible_to_basic_ostream<_Tp>::__ostream_type>::type std::operator<<(_Ostream&&, const _Tp&) [with _Ostream = std::basic_istream<char>&; _Tp = int]':
mat.cpp:53:13: required from here
/usr/include/c++/10/ostream:773:5: error: no type named 'type' in 'struct std::enable_if<false, void>'
In file included from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from mat.cpp:1:
/usr/include/c++/10/complex:554:5: note: candidate: 'template<class _Tp, class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::complex<_Tp>&)'
554 | operator<<(basic_ostream<_CharT, _Traits>& __os, const complex<_Tp>& __x)
| ^~~~~~~~
/usr/include/c++/10/complex:554:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
from mat.cpp:1:
/usr/include/c++/10/bitset:1540:5: note: candidate: 'template<class _CharT, class _Traits, long unsigned int _Nb> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::bitset<_Nb>&)'
1540 | operator<<(std::basic_ostream<_CharT, _Traits>& __os,
| ^~~~~~~~
/usr/include/c++/10/bitset:1540:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:72,
from mat.cpp:1:
/usr/include/c++/10/iomanip:79:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, std::_Resetiosflags)'
79 | operator<<(basic_ostream<_CharT, _Traits>& __os, _Resetiosflags __f)
| ^~~~~~~~
/usr/include/c++/10/iomanip:79:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[i];
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:72,
from mat.cpp:1:
/usr/include/c++/10/iomanip:109:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, std::_Setiosflags)'
109 | operator<<(basic_ostream<_CharT, _Traits>& __os, _Setiosflags __f)
| ^~~~~~~~
/usr/include/c++/10/iomanip:109:5: note: template argument deduction/substitution failed:
mat.cpp:53:13: note: 'std::istream' {aka 'std::basic_istream<char>'} is not derived from 'std::basic_ostream<_CharT, _Traits>'
53 | cin << A[