| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 42971 | PolyAtomicIon | Three Friends (BOI14_friends) | 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 <cmath>
#include <cstdio>
#include <string>
#include <unordered_set>
#define N 3111111
#define ll unsigned long long
#define pb push_back
#define mp make_pair
using namespace std;
ll n;
ll p = 31,h[N],pw[N];
ll mod = 1e9+7;
string s;
inline ll get_hash(int l,int r){
if( l > r )
return 0;
if( l == 0 )
return h[r] % mod;
else
return (h[r] - h[l-1] + mod) % mod;
}
unordered_set< pair<ll,int> > ans;
int main(){
cin >> n;
cin >> s;
pw[0] = 1;
for(int i=1; i<=n; i++){
pw[i] = pw[i-1];
pw[i] = (pw[i]*p) % mod;
}
h[0] = s[0]-'A'+1;
for(int i=1; i<n; i++){
h[i] = h[i-1];
h[i] = ( h[i] % mod + ((s[i] - 'A'+1)*pw[i]) % mod);
h[i] %= mod;
}
int md = n/2;
for(int i=0; i<=md; i++){
ll a1 = get_hash(0,i-1);
ll a2 = get_hash(md+1,md+1+i-1);
a1 = (a1 * pw[md+1]) % mod;
//cout << s.substr(0,i) << " " << s.substr(md+1,i) << " : ";
ll b1 = get_hash(i+1,i+1+md-i-1);
ll b2 = get_hash(md+1+i,md+1+i+md-i-1);
b1 = (b1 * pw[md]) % mod;
//cout << s.substr(i+1,md-i) << ' ' << s.substr( md+1+i,md-i ) << '\n';
//cout << i << " : " << a1 << ' ' << a2 << ' ' << b1 << ' ' << b2 << '\n';
if( a1 == a2 && b1 == b2 ){
ans.insert( mp(a2,md+1) );
}
}
int cur = 0;
for(int i=md; i<n; i++){
int a1 = get_hash(0,cur-1);
int a2 = get_hash(i-cur,i-1);
a1 = (a1 * pw[md]) % mod;
//cout << s.substr(0,cur) << " " << s.substr(i-cur,cur) << " : ";
int b1 = get_hash(cur,md-1);
int b2 = get_hash(i+1,n-1);
b1 = (b1 * pw[md+1]) % mod;
//cout << s.substr(cur,md-cur) << ' ' << s.substr( i+1,md-cur ) << '\n';
//cout << i << " : " << a1 << ' ' << a2 << ' ' << b1 << ' ' << b2 << '\n';
if( a1 == a2 && b1 == b2 ){
ans.insert( mp(a1,0) );
}
cur++;
}
if( ans.size() == 0 ){
cout << "NOT POSSIBLE";
}
else if( ans.size() > 1 ){
cout << "NOT UNIQUE";
}
else{
int id = ans.begin() -> second;
cout << s.substr(id,md);
}
return 0;
}
Compilation message (stderr)
In file included from /usr/include/c++/5/bits/hashtable.h:35:0,
from /usr/include/c++/5/unordered_set:47,
from friends.cpp:5:
/usr/include/c++/5/bits/hashtable_policy.h: In instantiation of 'struct std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > >':
/usr/include/c++/5/type_traits:137:12: required from 'struct std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > >'
/usr/include/c++/5/type_traits:148:38: required from 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
/usr/include/c++/5/bits/unordered_set.h:95:63: required from 'class std::unordered_set<std::pair<long long unsigned int, int> >'
friends.cpp:26:34: required from here
/usr/include/c++/5/bits/hashtable_policy.h:85:34: error: no match for call to '(const std::hash<std::pair<long long unsigned int, int> >) (const std::pair<long long unsigned int, int>&)'
noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
^
In file included from /usr/include/c++/5/bits/move.h:57:0,
from /usr/include/c++/5/bits/stl_pair.h:59,
from /usr/include/c++/5/bits/stl_algobase.h:64,
from /usr/include/c++/5/bits/char_traits.h:39,
from /usr/include/c++/5/ios:40,
from /usr/include/c++/5/ostream:38,
from /usr/include/c++/5/iostream:39,
from friends.cpp:1:
/usr/include/c++/5/type_traits: In instantiation of 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >':
/usr/include/c++/5/bits/unordered_set.h:95:63: required from 'class std::unordered_set<std::pair<long long unsigned int, int> >'
friends.cpp:26:34: required from here
/usr/include/c++/5/type_traits:148:38: error: 'value' is not a member of 'std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > >'
: public integral_constant<bool, !_Pp::value>
^
In file included from /usr/include/c++/5/unordered_set:48:0,
from friends.cpp:5:
/usr/include/c++/5/bits/unordered_set.h: In instantiation of 'class std::unordered_set<std::pair<long long unsigned int, int> >':
friends.cpp:26:34: required from here
/usr/include/c++/5/bits/unordered_set.h:95:63: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
^
/usr/include/c++/5/bits/unordered_set.h:102:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::key_type key_type;
^
/usr/include/c++/5/bits/unordered_set.h:103:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::value_type value_type;
^
/usr/include/c++/5/bits/unordered_set.h:104:43: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::hasher hasher;
^
/usr/include/c++/5/bits/unordered_set.h:105:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::key_equal key_equal;
^
/usr/include/c++/5/bits/unordered_set.h:106:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::allocator_type allocator_type;
^
/usr/include/c++/5/bits/unordered_set.h:111:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::pointer pointer;
^
/usr/include/c++/5/bits/unordered_set.h:112:50: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::const_pointer const_pointer;
^
/usr/include/c++/5/bits/unordered_set.h:113:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::reference reference;
^
/usr/include/c++/5/bits/unordered_set.h:114:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::const_reference const_reference;
^
/usr/include/c++/5/bits/unordered_set.h:115:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::iterator iterator;
^
/usr/include/c++/5/bits/unordered_set.h:116:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::const_iterator const_iterator;
^
/usr/include/c++/5/bits/unordered_set.h:117:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::local_iterator local_iterator;
^
/usr/include/c++/5/bits/unordered_set.h:118:57: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::const_local_iterator const_local_iterator;
^
/usr/include/c++/5/bits/unordered_set.h:119:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::size_type size_type;
^
/usr/include/c++/5/bits/unordered_set.h:120:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
typedef typename _Hashtable::difference_type difference_type;
^
/usr/include/c++/5/bits/unordered_set.h:274:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
operator=(initializer_list<value_type> __l)
^
/usr/include/c++/5/bits/unordered_set.h:368:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
emplace(_Args&&... __args)
^
/usr/include/c++/5/bits/unordered_set.h:412:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
insert(const value_type& __x)
^
/usr/include/c++/5/bits/unordered_set.h:416:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
insert(value_type&& __x)
^
/usr/include/c++/5/bits/unordered_set.h:471:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
insert(initializer_list<value_type> __l)
^
/usr/include/c++/5/bits/unordered_set.h:616:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
equal_range(const key_type& __x)
^
/usr/include/c++/5/bits/unordered_set.h:620:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<long long unsigned int, int> > >, std::__detail::__is_noexcept_hash<std::pair<long long unsigned int, int>, std::hash<std::pair<long long unsigned int, int> > > > >'
equal_range(const key_type& __x) const
^
friends.cpp: In function 'int main()':
friends.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<=n; i++){
^
friends.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<n; i++){
^
friends.cpp:65:34: error: no matching function for call to 'std::unordered_set<std::pair<long long unsigned int, int> >::insert(std::pair<long long unsigned int, int>)'
ans.insert( mp(a2,md+1) );
^
In file included from /usr/include/c++/5/unordered_set:48:0,
from friends.cpp:5:
/usr/include/c++/5/bits/unordered_set.h:460:2: note: candidate: template<class _InputIterator> void std::unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Value = std::pair<long long unsigned int, int>; _Hash = std::hash<std::pair<long long unsigned int, int> >; _Pred = std::equal_to<std::pair<long long unsigned int, int> >; _Alloc = std::allocator<std::pair<long long unsigned int, int> >]
insert(_InputIterator __first, _InputIterator __last)
^
/usr/include/c++/5/bits/unordered_set.h:460:2: note: template argument deduction/substitution failed:
friends.cpp:65:34: note: candidate expects 2 arguments, 1 provided
ans.insert( mp(a2,md+1) );
^
friends.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=md; i<n; i++){
^
friends.cpp:88:31: error: no matching function for call to 'std::unordered_set<std::pair<long long unsigned int, int> >::insert(std::pair<int, int>)'
ans.insert( mp(a1,0) );
^
In file included from /usr/include/c++/5/unordered_set:48:0,
from friends.cpp:5:
/usr/include/c++/5/bits/unordered_set.h:460:2: note: candidate: template<class _InputIterator> void std::unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Value = std::pair<long long unsigned int, int>; _Hash = std::hash<std::pair<long long unsigned int, int> >; _Pred = std::equal_to<std::pair<long long unsigned int, int> >; _Alloc = std::allocator<std::pair<long long unsigned int, int> >]
insert(_InputIterator __first, _InputIterator __last)
^
/usr/include/c++/5/bits/unordered_set.h:460:2: note: template argument deduction/substitution failed:
friends.cpp:88:31: note: candidate expects 2 arguments, 1 provided
ans.insert( mp(a1,0) );
^
friends.cpp:94:12: error: 'class std::unordered_set<std::pair<long long unsigned int, int> >' has no member named 'size'
if( ans.size() == 0 ){
^
friends.cpp:97:17: error: 'class std::unordered_set<std::pair<long long unsigned int, int> >' has no member named 'size'
else if( ans.size() > 1 ){
^
friends.cpp:101:20: error: 'class std::unordered_set<std::pair<long long unsigned int, int> >' has no member named 'begin'
int id = ans.begin() -> second;
^