#include "triples.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; vector<int> construct_range(int M, int K) { // ll N = M; // vector<int> vf; // vf.push_back(1); // for (ll i=1;i<N;i++) { // vf.push_back(i); // } // return vf; vector<int> vf(M,M-1); vector<ll> v0; ll tsum = 0; ll cv = 1; while (tsum<(4*M)) { v0.push_back(cv); tsum += cv; cv += 2; } for (ll x: v0) { for (ll y: v0) { ll xf = (x+y)/2; ll yf = (y-x)/2; if (yf>0 && xf<M) { vf[xf]=min(vf[xf],yf); } } } return vf; } long long count_triples(vector<int> H) { ll N = H.size(); ll ans = 0; //H[x]=z-x H[y]=z-y H[z]=y-x // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(z-x) && H[y]==(z-y) && H[z]==(y-x)) { // ans++; // } // } // } // } for (ll x=0;x<N;x++) { ll z = x+H[x]; if (z<N) { ll y=H[z]+x; if (y<N) { if ((H[y]+y)==z && x<y && y<z && (z-y)!=(y-x)) { ans++; } } } } //H[x]=z-x H[y]=y-x H[z]=z-y // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(z-x) && H[y]==(y-x) && H[z]==(z-y)) { // ans++; // } // } // } // } for (ll x=0;x<N;x++) { ll z = x+H[x]; if (z<N) { ll y = z-H[z]; if (y>=0) { if (H[y]==(y-x) && x<y && y<z) { ans++; } } } } //H[x]=y-x, H[y]=z-x, H[z]=z-y // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(y-x) && H[y]==(z-x) && H[z]==(z-y)) { // ans++; // } // } // } // } for (ll x=0;x<N;x++) { ll y=x+H[x]; if (y<N) { ll z = x+H[y]; if (z<N) { if (H[z]==(z-y) && x<y && y<z && (z-y)!=(y-x)) { ans++; } } } } //H[x]=y-x, H[y]=z-y, H[z]=z-x // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(y-x) && H[y]==(z-y) && H[z]==(z-x)) { // ans++; // } // } // } // } for (ll x=0;x<N;x++) { ll y=x+H[x]; if (y<N) { ll z = y+H[y]; if (z<N) { if (H[z]==(z-x) && x<y && y<z && (z-y)!=(y-x)) { ans++; } } } } //H[x]=z-y, H[y]=y-x, H[z]=z-x // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(z-y) && H[y]==(y-x) && H[z]==(z-x)) { // ans++; // } // } // } // } for (ll y=0;y<N;y++) { ll x = y-H[y]; if (x>=0) { ll z = y+H[x]; if (z<N) { if (H[z]==(z-x) && x<y && y<z) { ans++; } } } } //H[x]=z-y, H[y]=z-x, H[z]=y-x // for (ll x=0;x<N;x++) { // for (ll y=(x+1);y<N;y++) { // for (ll z=(y+1);z<N;z++) { // if (H[x]==(z-y) && H[y]==(z-x) && H[z]==(y-x)) { // ans++; // } // } // } // } vector<ll> va[N]; vector<ll> vb[N]; for (ll x=0;x<N;x++) { if ((x+H[x])<N) { va[x+H[x]].push_back(x); } if ((x-H[x])>=0) { vb[x-H[x]].push_back(x); } } for (ll r=0;r<N;r++) { ll A = va[r].size(); ll B=vb[r].size(); if ((A*B)>=N) { for (ll x0=0;x0<N;x0++) { ll y0 = H[x0]; if ((x0+y0)%2==(r%2)) { ll x1 = (x0+y0+r)/2; ll y1 = (x0+y0-r)/2; ll x2 = (r+x0-y0)/2; ll y2 = (y0-x0+r)/2; if (x1<N && x1>=0 && x2<N && x2>=0) { if (H[x1]==y1 && H[x2]==y2) { ans++; } } } } } else { //manual: A*B for (ll xa: va[r]) { ll ya = H[xa]; for (ll xb: vb[r]) { ll yb = H[xb]; ll xf = xa+xb-r; ll yf = ya+yb; if (xf>=0 && xf<N) { if (H[xf]==yf) { ans++; } } } } } } return ans; }

triples.cpp: In function 'std::vector<int> construct_range(int, int)':
triples.cpp:28:27: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, ll&)'
   28 |                 vf[xf]=min(vf[xf],yf);
      |                        ~~~^~~~~~~~~~~
In file included from /usr/include/c++/13/vector:62,
                 from triples.h:1,
                 from triples.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
triples.cpp:28:27: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   28 |                 vf[xf]=min(vf[xf],yf);
      |                        ~~~^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
triples.cpp:28:27: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   28 |                 vf[xf]=min(vf[xf],yf);
      |                        ~~~^~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from triples.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
triples.cpp:28:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   28 |                 vf[xf]=min(vf[xf],yf);
      |                        ~~~^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
triples.cpp:28:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   28 |                 vf[xf]=min(vf[xf],yf);
      |                        ~~~^~~~~~~~~~~