Submission #340035

#TimeUsernameProblemLanguageResultExecution timeMemory
340035bigDuckGondola (IOI14_gondola)C++14
Compilation error
0 ms0 KiB
#include "gondola.h" #include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount ll mod=((ll)1000000000)+9; map<int, int> cnt_valid; int valid(int n, int inputSeq[]) { vector<pii> v; for(int i=0; i<n; i++){ if(cnt_valid[inputSeq[i]]>0 ){ return 0; } cnt_valid[inputSeq[i] ]++; if(inputSeq[i]<=n){ v.pb({inputSeq[i], i} ); } } int ls=0; if(v[0]==1){ ls=1; } for(int i=0; i<v.size(); i++){ if(i>0){ if(v[i].ft<v[i-1].ft){ls++;} if( abs(v[i].ft-( (v[i-1].ft==n)?(0):(v[i-1].ft) ) )!=abs(v[i].sc-v[i-1].sc) ){return 0;} } if(ls>1){ return 0; } } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int pt=0, crd=0; for(int i=0; i<n; i++){ if(gondolaSeq[i]<=n){ pt=gondolaSeq[i], crd=i; break; } } int initial[100010]; if(pt==0){ for(int i=0; i<n; i++){ initial[i]=i+1; } } else{ for(int i=crd-pt+1, cnt=1; cnt<=n; i++){ i+=n; i%=n; initial[i]=cnt; cnt++; } } set<pii> s; for(int i=0; i<n; i++){ if(gondolaSeq[i]>n){ s.insert({gondolaSeq[i], i} ); } } if(s.empty()){ return 0; } int cnt=n+1; for(auto it=s.begin(); it!=s.end(); it++){ while(cnt<(it->ft) ){ replacementSeq[cnt-n-1]=initial[it->sc]; initial[it->sc]=cnt; cnt++; } replacementSeq[cnt-n-1]=initial[it->sc]; initial[it->sc]=cnt; cnt++; } return cnt-1-n; } //---------------------- ll exp(ll x, ll e){ if(e==0){ return 1; } if(e==1){ return x%mod; } return (exp(x, e%2)*(exp( (x*x)%mod, e/2) ) )%mod ; } int countReplacement(int n, int inputSeq[]) { ll p=n; if(valid(n, inputSeq)==0){ return 0; } multiset<ll> s; for(int i=0; i<n; i++){ if(inputSeq[i]>n){s.insert({inputSeq[i]});} else{ p--; } } ll ac=n+1; ll res=1; if( p==n ){ res=n; } for(auto it=s.begin(); it!=s.end(); it++){ res=(res*( exp(p, ((*it)-1)-ac+1 ) ) )%mod; ac=(*it)+1; p--; } return res; }

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:31:12: error: no match for 'operator==' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} and 'int')
   31 |     if(v[0]==1){
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/regex.h:1026:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1026 |     operator==(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1026:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/regex.h:1099:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
 1099 |     operator==(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1099:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/regex.h:1173:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1173 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1173:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/regex.h:1247:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
 1247 |     operator==(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1247:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/regex.h:1321:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1321 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1321:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/regex.h:1395:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
 1395 |     operator==(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1395:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/regex.h:1473:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator==(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1473 |     operator==(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1473:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/regex.h:1991:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator==(const std::__cxx11::match_results<_BiIter, _Alloc>&, const std::__cxx11::match_results<_BiIter, _Alloc>&)'
 1991 |     operator==(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1991:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/iosfwd:40,
                 from /usr/include/c++/9/ios:38,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/postypes.h:222:5: note: candidate: 'template<class _StateT> bool std::operator==(const std::fpos<_StateT>&, const std::fpos<_StateT>&)'
  222 |     operator==(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/9/bits/postypes.h:222:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::fpos<_StateT>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/stl_pair.h:448:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator==(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  448 |     operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:448:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   mismatched types 'const std::pair<_T1, _T2>' and 'int'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/stl_iterator.h:325:5: note: candidate: 'template<class _Iterator> bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  325 |     operator==(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:325:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/stl_iterator.h:363:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator==(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  363 |     operator==(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:363:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/stl_iterator.h:1139:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1139 |     operator==(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1139:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::move_iterator<_IteratorL>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/stl_iterator.h:1145:5: note: candidate: 'template<class _Iterator> bool std::operator==(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1145 |     operator==(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1145:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::move_iterator<_IteratorL>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/string:41,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/allocator.h:168:5: note: candidate: 'template<class _T1, class _T2> bool std::operator==(const std::allocator<_CharT>&, const std::allocator<_T2>&)'
  168 |     operator==(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/9/bits/allocator.h:168:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::allocator<_CharT>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/basic_string.h:6141: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>&)'
 6141 |     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6141:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/basic_string.h:6149:5: note: candidate: 'template<class _CharT> typename __gnu_cxx::__enable_if<std::__is_char<_Tp>::__value, bool>::__type std::operator==(const std::__cxx11::basic_string<_CharT>&, const std::__cxx11::basic_string<_CharT>&)'
 6149 |     operator==(const basic_string<_CharT>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6149:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::basic_string<_CharT>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3:
/usr/include/c++/9/bits/basic_string.h:6163:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator==(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
 6163 |     operator==(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6163:5: note:   template argument deduction/substitution failed:
gondola.cpp:31:14: note:   mismatched types 'const _CharT*' and 'std::pair<int, int>'
   31 |     if(v[0]==1){
      |              ^
In file included from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from gondola.cpp:3