# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
133057 | 2019-07-20T06:08:55 Z | E869120 | Necklace (Subtask 1-3) (BOI19_necklace1) | C++14 | 컴파일 오류 |
0 ms | 0 KB |
#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
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; } ~~~~~~^~~~~~~