| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 280497 | ElyesChaabouni | Ideal city (IOI12_city) | 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.
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define ordered_set tree<int, null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update>
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
#define INV_10 299473306
#define INF 1000000000
#define PI 3.14159265358979323846
using namespace std;
int DistanceSum(int N, int *X, int *Y)
{
if(N <= 2000)
{
vector<int>v[N];
for(int j = 0; j < N; j++)
{
for(int k = j+1; k< N; k++)
{
long long x1=abs(X[j]-X[k]), y1=abs(Y[j]-Y[k]);
long long dis=x1+y1;
if(dis==1)
{
v[k].push_back(j);
v[j].push_back(k);
}
}
}
long long ans=0;
for(int i = 0; i < N; i++)
{
//cout << i << ' ' << X[i] << ' ' << Y[i] << '\n';
unordered_set<int>s;
int nb=1, idx=0;
vector<int>bfs;
bfs.push_back(i);
bool ok=1;
s.insert(i);
while(bfs.size()!=N)
{
//cout << nb << '\n';
int l=bfs.size();
for(int j = idx; j < l; j++)
{
//cout << bfs[j].first << ' ' << bfs[j].second << '\n';
for(int k = 0; k < v[bfs[j]].size(); k++)
{
if(!s.count(v[bfs[j]][k]))
{
s.insert(v[bfs[j]][k]);
if(v[bfs[j]][k] < i)
ans+=nb;
bfs.push_back(v[bfs[j]][k]);
}
}
}
nb++;
idx=l;
}
ans%= 1000000000;
}
//ans*=( 1000000000);
ans%= 1000000000;
return ans;
}
else
{
int x_min=2147483646, x_max=0, y_min=2147483646, y_max=0;
for(int i = 0; i < N; i++)
{
x_min=min(x_min, X[i]);
x_max=max(x_max, X[i]);
y_min=min(y_min, Y[i]);
y_max=max(y_max, Y[i]);
}
/*int a[y_max-y_min+1];
int b[y_max-y_min+1];
for(int i = 0; i < y_max-y_min+1; i++)
{
a[i]=-1;
}*/
vector<pair<int, long long> >v[x_max-x_min+1];
for(int i = 0; i < N; i++)
{
v[X[i]].push_back(Y[i], 0LL);
}
for(int i = 0; i < x_max-x_min+1; i++)
sort(v[i].begin(), v[i].end());
long long ans=0;
long long nb=0;
for(int i = x_min; i <= x_max; i++)
{
for(int j = 0; j < v[i-x_min].size(); j++)
{
long long cu=j, cu1=(v[i-x_min].size()-j-1);
cu1*=(cu1+1);
cu*=(j+1);
cu/=2;
cu1/=2;
ans+=cu;
ans%=1000000000;
long long cu2=cu+cu1;
cu2%=1000000000;
v[i-x_min][j].second=cu2;
if(i!=x_min)
{
vector<pair<int, int> >::iterator it=lower_bound(v[i-x_min-1].begin(), v[i-x_min-1].end(), make_pair(v[i-x_min][j].first, 0LL));
if(it==v[i-x_min-1].end())
it=prev(it);
long long dis=1+abs(v[i-x_min][j]-(*it).first);
long long ans+=dis*nb+(*it).second;
ans%=1000000000;
v[i-x_min][j].second+=(dis*nb+(*it).second);
}
}
nb+=v[i-x_min].size();
}
return ans;
}
}
Compilation message (stderr)
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:41:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | while(bfs.size()!=N)
| ~~~~~~~~~~^~~
city.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int k = 0; k < v[bfs[j]].size(); k++)
| ~~^~~~~~~~~~~~~~~~~~
city.cpp:39:9: warning: unused variable 'ok' [-Wunused-variable]
39 | bool ok=1;
| ^~
city.cpp:87:31: error: no matching function for call to 'std::vector<std::pair<int, long long int> >::push_back(int&, long long int)'
87 | v[X[i]].push_back(Y[i], 0LL);
| ^
In file included from /usr/include/c++/9/vector:67,
from /usr/include/c++/9/queue:61,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
from city.cpp:2:
/usr/include/c++/9/bits/stl_vector.h:1184:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, long long int>]'
1184 | push_back(const value_type& __x)
| ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1184:7: note: candidate expects 1 argument, 2 provided
/usr/include/c++/9/bits/stl_vector.h:1200:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, long long int>]'
1200 | push_back(value_type&& __x)
| ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1200:7: note: candidate expects 1 argument, 2 provided
city.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int j = 0; j < v[i-x_min].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~
city.cpp:109:54: error: conversion from '__normal_iterator<std::pair<int, long long int>*,vector<pair<[...],long long int>>>' to non-scalar type '__normal_iterator<std::pair<int, int>*,vector<pair<[...],int>>>' requested
109 | vector<pair<int, int> >::iterator it=lower_bound(v[i-x_min-1].begin(), v[i-x_min-1].end(), make_pair(v[i-x_min][j].first, 0LL));
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:110:11: error: no match for 'operator==' (operand types are 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} and 'std::vector<std::pair<int, long long int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, long long int>*, std::vector<std::pair<int, long long int> > >'})
110 | if(it==v[i-x_min-1].end())
| ~~^~~~~~~~~~~~~~~~~~~~
| | |
| | __normal_iterator<std::pair<int, long long int>*,vector<pair<[...],long long int>>>
| __normal_iterator<std::pair<int, int>*,vector<pair<[...],int>>>
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
110 | if(it==v[i-x_min-1].end())
| ^
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
110 | if(it==v[i-x_min-1].end())
| ^
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
110 | if(it==v[i-x_min-1].end())
| ^
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, long long int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, long long int>*, std::vector<std::pair<int, long long int> > >'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
110 | if(it==v[i-x_min-1].end())
| ^
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
110 | if(it==v[i-x_min-1].end())
| ^
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, long long int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, long long int>*, std::vector<std::pair<int, long long int> > >'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
110 | if(it==v[i-x_min-1].end())
| ^
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
110 | if(it==v[i-x_min-1].end())
| ^
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
110 | if(it==v[i-x_min-1].end())
| ^
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 city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::fpos<_StateT>'
110 | if(it==v[i-x_min-1].end())
| ^
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 city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::pair<_T1, _T2>'
110 | if(it==v[i-x_min-1].end())
| ^
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 city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::reverse_iterator<_Iterator>'
110 | if(it==v[i-x_min-1].end())
| ^
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 city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::reverse_iterator<_Iterator>'
110 | if(it==v[i-x_min-1].end())
| ^
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 city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::move_iterator<_IteratorL>'
110 | if(it==v[i-x_min-1].end())
| ^
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 city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std::move_iterator<_IteratorL>'
110 | if(it==v[i-x_min-1].end())
| ^
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 city.cpp:2:
/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:
city.cpp:110:30: note: 'std::vector<std::pair<int, int> >::iterator' {aka '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >'} is not derived from 'const std