| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 705045 | MtSaka | Monster Game (JOI21_monster) | 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>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;i--)
#define all(x) begin(x),end(x)
using ll=long long;
using namespace std;
using ull=unsigned long long;
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b)?a=b,true:false;}
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b)?a=b,true:false;}
#include "monster.h"
map<pair<int,int>,bool>mp;
bool ask(int a,int b){
if(mp.count({a,b}))return mp[{a,b}];
if(mp.count({b,a}))return mp[{b,a}];
return mp[{a,b}]=Query(a,b);
}
void merge(vector<int>&v){
if(v.size()==1)return;
int mid=v.size()/2;
auto l(v.begin(),v.begin()+mid),r(v.begin()+mid,v.end());
merge(l),merge(r);
int i=0,j=0;
rep(k,0,v.size()){
if(i==l.size())v[k]=r[j++];
else if(j==r.size())v[k]=l[i++];
else if(ask(l[i],r[j]))v[k]=r[j++];
else v[k]=l[i++];
}
return;
}
int sol2(const vector<int>&id){
int n=id.size();
vector<int>cnt(n,0);
vector<vector<int>>a(n,vector<int>(n,0));
rep(i,0,n)rep(j,i+1,n){
bool f=ask(id[i],id[j]);
if(f)cnt[i]++;
else cnt[j]++;
a[i][j]=f;
a[j][i]=!f;
}
rep(i,0,n)if(cnt[i]==1){
rep(j,i+1,n)if(cnt[j]==1){
if(a[i][j])return i
else return j;
break;
}
return i;
break;
}
return -1;
}
vector<int>Solve(int n){
vector<int>id(n);
iota(id.begin(),id.end(),0);
merge(id);
vector<int>tmp(id.begin(),id.begin()+min(10,n));
int mi=sol2(tmp);
int start=id[mi];
id.erase(id.begin()+mi);
id.insert(id.begin(),start);
rep(i,1,n){
ll j=i;
while(j<n&&ask(id[j],start))j++;
reverse(id.begin()+i,id.begin()+min(j+1,n));
if(j==n)break;
start=v[j];
i=j;
}
vector<int>ret(n);
rep(i,0,n)ret[id[i]]=i;
return ret;
}
Compilation message (stderr)
monster.cpp: In function 'void merge(std::vector<int>&)':
monster.cpp:22:33: error: expression list treated as compound expression in initializer [-fpermissive]
22 | auto l(v.begin(),v.begin()+mid),r(v.begin()+mid,v.end());
| ^
monster.cpp:22:33: error: no matching function for call to '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::__normal_iterator(std::vector<int>::iterator, __gnu_cxx::__normal_iterator<int*, std::vector<int> >)'
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:959:9: note: candidate: 'template<class _Iter> __gnu_cxx::__normal_iterator<_Iterator, _Container>::__normal_iterator(const __gnu_cxx::__normal_iterator<_Iter, typename __gnu_cxx::__enable_if<std::__are_same<_Iter, typename _Container::pointer>::__value, _Container>::__type>&) [with _Iter = _Iter; _Iterator = int*; _Container = std::vector<int>]'
959 | __normal_iterator(const __normal_iterator<_Iter,
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:959:9: note: template argument deduction/substitution failed:
monster.cpp:22:33: note: candidate expects 1 argument, 2 provided
22 | auto l(v.begin(),v.begin()+mid),r(v.begin()+mid,v.end());
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:953:7: note: candidate: '__gnu_cxx::__normal_iterator<_Iterator, _Container>::__normal_iterator(const _Iterator&) [with _Iterator = int*; _Container = std::vector<int>]'
953 | __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:953:7: note: candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_iterator.h:949:26: note: candidate: 'constexpr __gnu_cxx::__normal_iterator<_Iterator, _Container>::__normal_iterator() [with _Iterator = int*; _Container = std::vector<int>]'
949 | _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:949:26: note: candidate expects 0 arguments, 2 provided
/usr/include/c++/10/bits/stl_iterator.h:930:11: note: candidate: 'constexpr __gnu_cxx::__normal_iterator<int*, std::vector<int> >::__normal_iterator(const __gnu_cxx::__normal_iterator<int*, std::vector<int> >&)'
930 | class __normal_iterator
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:930:11: note: candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_iterator.h:930:11: note: candidate: 'constexpr __gnu_cxx::__normal_iterator<int*, std::vector<int> >::__normal_iterator(__gnu_cxx::__normal_iterator<int*, std::vector<int> >&&)'
/usr/include/c++/10/bits/stl_iterator.h:930:11: note: candidate expects 1 argument, 2 provided
monster.cpp:22:58: error: expression list treated as compound expression in initializer [-fpermissive]
22 | auto l(v.begin(),v.begin()+mid),r(v.begin()+mid,v.end());
| ^
monster.cpp:22:58: error: no matching function for call to '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::__normal_iterator(__gnu_cxx::__normal_iterator<int*, std::vector<int> >, std::vector<int>::iterator)'
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:959:9: note: candidate: 'template<class _Iter> __gnu_cxx::__normal_iterator<_Iterator, _Container>::__normal_iterator(const __gnu_cxx::__normal_iterator<_Iter, typename __gnu_cxx::__enable_if<std::__are_same<_Iter, typename _Container::pointer>::__value, _Container>::__type>&) [with _Iter = _Iter; _Iterator = int*; _Container = std::vector<int>]'
959 | __normal_iterator(const __normal_iterator<_Iter,
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:959:9: note: template argument deduction/substitution failed:
monster.cpp:22:58: note: candidate expects 1 argument, 2 provided
22 | auto l(v.begin(),v.begin()+mid),r(v.begin()+mid,v.end());
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:953:7: note: candidate: '__gnu_cxx::__normal_iterator<_Iterator, _Container>::__normal_iterator(const _Iterator&) [with _Iterator = int*; _Container = std::vector<int>]'
953 | __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:953:7: note: candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_iterator.h:949:26: note: candidate: 'constexpr __gnu_cxx::__normal_iterator<_Iterator, _Container>::__normal_iterator() [with _Iterator = int*; _Container = std::vector<int>]'
949 | _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:949:26: note: candidate expects 0 arguments, 2 provided
/usr/include/c++/10/bits/stl_iterator.h:930:11: note: candidate: 'constexpr __gnu_cxx::__normal_iterator<int*, std::vector<int> >::__normal_iterator(const __gnu_cxx::__normal_iterator<int*, std::vector<int> >&)'
930 | class __normal_iterator
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:930:11: note: candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_iterator.h:930:11: note: candidate: 'constexpr __gnu_cxx::__normal_iterator<int*, std::vector<int> >::__normal_iterator(__gnu_cxx::__normal_iterator<int*, std::vector<int> >&&)'
/usr/include/c++/10/bits/stl_iterator.h:930:11: note: candidate expects 1 argument, 2 provided
monster.cpp:23:10: error: no matching function for call to 'merge(__gnu_cxx::__normal_iterator<int*, std::vector<int> >&)'
23 | merge(l),merge(r);
| ^
monster.cpp:19:6: note: candidate: 'void merge(std::vector<int>&)'
19 | void merge(vector<int>&v){
| ^~~~~
monster.cpp:19:24: note: no known conversion for argument 1 from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' to 'std::vector<int>&'
19 | void merge(vector<int>&v){
| ~~~~~~~~~~~~^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4944:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter)'
4944 | merge(_InputIterator1 __first1, _InputIterator1 __last1,
| ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4944:5: note: template argument deduction/substitution failed:
monster.cpp:23:10: note: candidate expects 5 arguments, 1 provided
23 | merge(l),merge(r);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4995:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter, class _Compare> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare)'
4995 | merge(_InputIterator1 __first1, _InputIterator1 __last1,
| ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4995:5: note: template argument deduction/substitution failed:
monster.cpp:23:10: note: candidate expects 6 arguments, 1 provided
23 | merge(l),merge(r);
| ^
In file included from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator, class _Compare> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator, _Compare)'
412 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
| ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note: template argument deduction/substitution failed:
monster.cpp:23:10: note: candidate expects 7 arguments, 1 provided
23 | merge(l),merge(r);
| ^
In file included from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator)'
417 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
| ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note: template argument deduction/substitution failed:
monster.cpp:23:10: note: candidate expects 6 arguments, 1 provided
23 | merge(l),merge(r);
| ^
monster.cpp:23:19: error: no matching function for call to 'merge(__gnu_cxx::__normal_iterator<int*, std::vector<int> >&)'
23 | merge(l),merge(r);
| ^
monster.cpp:19:6: note: candidate: 'void merge(std::vector<int>&)'
19 | void merge(vector<int>&v){
| ^~~~~
monster.cpp:19:24: note: no known conversion for argument 1 from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' to 'std::vector<int>&'
19 | void merge(vector<int>&v){
| ~~~~~~~~~~~~^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4944:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter)'
4944 | merge(_InputIterator1 __first1, _InputIterator1 __last1,
| ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4944:5: note: template argument deduction/substitution failed:
monster.cpp:23:19: note: candidate expects 5 arguments, 1 provided
23 | merge(l),merge(r);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4995:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter, class _Compare> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare)'
4995 | merge(_InputIterator1 __first1, _InputIterator1 __last1,
| ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4995:5: note: template argument deduction/substitution failed:
monster.cpp:23:19: note: candidate expects 6 arguments, 1 provided
23 | merge(l),merge(r);
| ^
In file included from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator, class _Compare> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator, _Compare)'
412 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
| ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note: template argument deduction/substitution failed:
monster.cpp:23:19: note: candidate expects 7 arguments, 1 provided
23 | merge(l),merge(r);
| ^
In file included from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator)'
417 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
| ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note: template argument deduction/substitution failed:
monster.cpp:23:19: note: candidate expects 6 arguments, 1 provided
23 | merge(l),merge(r);
| ^
monster.cpp:26:13: error: 'class __gnu_cxx::__normal_iterator<int*, std::vector<int> >' has no member named 'size'
26 | if(i==l.size())v[k]=r[j++];
| ^~~~
monster.cpp:27:18: error: 'class __gnu_cxx::__normal_iterator<int*, std::vector<int> >' has no member named 'size'
27 | else if(j==r.size())v[k]=l[i++];
| ^~~~
monster.cpp: In function 'int sol2(const std::vector<int>&)':
monster.cpp:46:26: error: expected ';' before 'else'
46 | if(a[i][j])return i
| ^
| ;
47 | else return j;
| ~~~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:67:46: error: no matching function for call to 'min(ll, int&)'
67 | reverse(id.begin()+i,id.begin()+min(j+1,n));
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
monster.cpp:67:46: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
67 | reverse(id.begin()+i,id.begin()+min(j+1,n));
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
monster.cpp:67:46: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
67 | reverse(id.begin()+i,id.begin()+min(j+1,n));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
monster.cpp:67:46: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
67 | reverse(id.begin()+i,id.begin()+min(j+1,n));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from monster.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
monster.cpp:67:46: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
67 | reverse(id.begin()+i,id.begin()+min(j+1,n));
| ^
monster.cpp:69:11: error: 'v' was not declared in this scope
69 | start=v[j];
| ^