| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 133057 | E869120 | Necklace (Subtask 1-3) (BOI19_necklace1) | C++14 | 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 <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const long long mod = 2147483647LL;
string S, T;
vector<pair<int, int>> vec[3009];
long long power[3009];
void init() {
power[0] = 1LL;
for (int i = 1; i <= 3000; i++) power[i] = (100LL * power[i - 1]) % mod;
}
long long hash_val(string &U) {
long long r = 0;
for (int i = 0; i < U.size(); i++) {
r *= 100LL;
r += (long long)(U[i] - 'a' + 1LL);
r %= mod;
}
return r;
}
vector<long long> get_substring(string &U) {
vector<long long> a, b, c;
a.push_back(0);
for (int i = 0; i < U.size(); i++) {
a.push_back((100LL * a[a.size() - 1] + (long long)(U[i] - 'a' + 1)) % mod);
}
b.push_back(0);
for (int i = U.size() - 1; i >= 0; i--) {
b.push_back((b[b.size() - 1] + power[U.size() - 1 - i] * (long long)(U[i] - 'a' + 1)) % mod);
}
reverse(b.begin(), b.end());
for (int i = 0; i < U.size(); i++) {
long long s = a[i] + power[i] * b[i];
s %= mod;
c.push_back(s);
}
return c;
}
int main() {
init();
cin >> S >> T;
for (int i = 0; i < S.size(); i++) {
string G = "";
for (int j = i + 1; j <= S.size(); j++) {
G += S[j - 1];
vector<long long> V1 = get_substring(G);
for (int k = 0; k < V1.size(); k++) vec[j - i].push_back(make_pair(V1[k], i));
}
}
for (int i = 0; i <= S.size(); i++) sort(vec[i].begin(), vec[i].end());
int maxn = 0; pair<int, int> maxid = make_pair(-1, -1);
for (int i = 0; i < T.size(); i++) {
string G = "";
for (int j = i + 1; j <= T.size(); j++) {
G += T[j - 1];
long long v = hash_val(G);
int pos1 = lower_bound(vec[j - i].begin(), vec[j - i].end(), make_pair((int)v, 0)) - vec[j - i].begin();
if (pos1 < vec[j - i].size() && vec[j - i][pos1].first == v) {
if (maxn < j - i) {
maxn = j - i;
maxid = make_pair(vec[j - i][pos1].second, i);
}
}
}
}
for (int i = 1; i <= T.size(); i++) {
string G = "";
for (int j = i - 1; j >= 0; j--) {
G += T[j];
long long v = hash_val(G);
int pos1 = lower_bound(vec[i - j].begin(), vec[i - j].end(), make_pair(v, 0)) - vec[i - j].begin();
if (pos1 < vec[i - j].size() && vec[i - j][pos1].first == v) {
if (maxn < i - j) {
maxn = i - j;
maxid = make_pair(vec[i - j][pos1].second, j);
}
}
}
}
cout << maxn << endl;
cout << maxid.first << " " << maxid.second << endl;
return 0;
}
Compilation message (stderr)
necklace.cpp: In function 'long long int hash_val(std::__cxx11::string&)':
necklace.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < U.size(); i++) {
~~^~~~~~~~~~
necklace.cpp: In function 'std::vector<long long int> get_substring(std::__cxx11::string&)':
necklace.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < U.size(); i++) {
~~^~~~~~~~~~
necklace.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < U.size(); i++) {
~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < S.size(); i++) {
~~^~~~~~~~~~
necklace.cpp:54:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i + 1; j <= S.size(); j++) {
~~^~~~~~~~~~~
necklace.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < V1.size(); k++) vec[j - i].push_back(make_pair(V1[k], i));
~~^~~~~~~~~~~
necklace.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i <= S.size(); i++) sort(vec[i].begin(), vec[i].end());
~~^~~~~~~~~~~
necklace.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < T.size(); i++) {
~~^~~~~~~~~~
necklace.cpp:65:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i + 1; j <= T.size(); j++) {
~~^~~~~~~~~~~
necklace.cpp:70:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos1 < vec[j - i].size() && vec[j - i][pos1].first == v) {
~~~~~^~~~~~~~~~~~~~~~~~~
necklace.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i <= T.size(); i++) {
~~^~~~~~~~~~~
necklace.cpp:86:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos1 < vec[i - j].size() && vec[i - j][pos1].first == v) {
~~~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Value = const std::pair<long long int, int>]':
/usr/include/c++/7/bits/stl_algobase.h:959:14: required from '_ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Tp = std::pair<long long int, int>; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
/usr/include/c++/7/bits/stl_algobase.h:993:32: required from '_ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Tp = std::pair<long long int, int>]'
necklace.cpp:85:80: required from here
/usr/include/c++/7/bits/predefined_ops.h:65:22: error: no match for 'operator<' (operand types are 'std::pair<int, int>' and 'const std::pair<long long int, int>')
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'std::pair<int, int>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: candidate: template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'std::pair<int, int>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/vector:64:0,
from necklace.cpp:3:
/usr/include/c++/7/bits/stl_vector.h:1613:5: note: candidate: template<class _Tp, class _Alloc> bool std::operator<(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)
operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
^~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:1613:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'std::pair<int, int>' is not derived from 'const std::vector<_Tp, _Alloc>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/ios_base.h:46:0,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/system_error:282:3: note: candidate: bool std::operator<(const std::error_condition&, const std::error_condition&)
operator<(const error_condition& __lhs,
^~~~~~~~
/usr/include/c++/7/system_error:282:3: note: no known conversion for argument 1 from 'std::pair<int, int>' to 'const std::error_condition&'
/usr/include/c++/7/system_error:208:3: note: candidate: bool std::operator<(const std::error_code&, const std::error_code&)
operator<(const error_code& __lhs, const error_code& __rhs) noexcept
^~~~~~~~
/usr/include/c++/7/system_error:208:3: note: no known conversion for argument 1 from 'std::pair<int, int>' to 'const std::error_code&'
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/basic_string.h:6107:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
operator<(const _CharT* __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:6107:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: mismatched types 'const _CharT*' and 'std::pair<int, int>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/basic_string.h:6095:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:6095:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/string:52:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/basic_string.h:6082:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:6082:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:1148:5: note: candidate: template<class _Iterator> bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)
operator<(const move_iterator<_Iterator>& __x,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:1148:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'std::pair<int, int>' is not derived from 'const std::move_iterator<_IteratorL>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:1142:5: note: candidate: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)
operator<(const move_iterator<_IteratorL>& __x,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:1142:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'std::pair<int, int>' is not derived from 'const std::move_iterator<_IteratorL>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:343:5: note: candidate: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)
operator<(const reverse_iterator<_IteratorL>& __x,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:343:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'std::pair<int, int>' is not derived from 'const std::reverse_iterator<_Iterator>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:305:5: note: candidate: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
operator<(const reverse_iterator<_Iterator>& __x,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:305:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'std::pair<int, int>' is not derived from 'const std::reverse_iterator<_Iterator>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/stl_pair.h:449:5: note: candidate: template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
^~~~~~~~
/usr/include/c++/7/bits/stl_pair.h:449:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from necklace.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: deduced conflicting types for parameter '_T1' ('int' and 'long long int')
{ return *__it < __val; }
~~~~~~^~~~~~~