Submission #787735

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
787735	2023-07-19T11:53:30 Z	sadsa	Rice Hub (IOI11_ricehub)	C++17	Compilation error	0 ms	0 KB

ricehub

#include "ricehub.h"

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

using i64 = long long;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    //((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
    out << '(' << pr.first << ", " << pr.second << ')';
    return out;
}

int besthub(int R, int L, int XCa[], long long B) {
    vi X(XCa, XCa + R);
    vi hub_count(L+2);

    for (auto Xi : X) {
        ++hub_count[Xi];
    }

    vi lreward(L+2);
    vl lcost(L+2);
    for (int i = 1; i <= L; ++i) {
        lreward[i] = lreward[i-1] + hub_count[i];
        lcost[i] = lcost[i-1] + lreward[i-1];
    }

    vi rreward(L+2);
    vl rcost(L+2);
    for (int i = L; i >= 1; --i) {
        rreward[i] = rreward[i+1] + hub_count[i];
        rcost[i] = rcost[i+1] + rreward[i+1];
    }

    DBG(X);
    DBG(hub_count);
    DBG("left:");
    DBG(lreward);
    DBG(lcost);
    DBG("right:");
    DBG(rreward);
    DBG(rcost);

    auto lquery = [&] (int Xm, int Xl) {
        i64 dist = Xm-Xl;
        i64 maxcost = lcost[Xm] - lcost[Xl] - dist*lreward[Xl-1];
        i64 mincost = hub_count[Xl]? (maxcost-(hub_count[Xl]-1)*dist): maxcost;
        return tuple{lreward[Xm]-lreward[Xl-1], mincost, maxcost};
    };

    auto rquery = [&] (int Xm, int Xr) {
        i64 dist = Xr-Xm;
        i64 maxcost = rcost[Xm] - rcost[Xr] - dist * rreward[Xr+1];
        i64 mincost = hub_count[Xr]? (maxcost-(hub_count[Xr]-1)*dist): maxcost;
        return tuple{rreward[Xm]-rreward[Xr+1], mincost, maxcost};
    };

    auto range_query = [&] (int Xm, int Xl, int Xr) {
        auto [lr, lcmin, lcmax] = lquery(Xm, Xl);
        auto [rr, rcmin, rcmax] = rquery(Xm, Xr);
        i64 total_cost = lcmax + rcmax;

        if (Xl == 1 && Xr == 4 && Xm == 3) {
            DBG(lcmin, lcmax, rcmin, rcmax);
            DBG(total_cost);
            DBG(B);
            DBG("12312312321321321312321");
        }
        if (total_cost <= B) {
            return pair{lr+rr-hub_count[Xm], total_cost};
        } else if (lcmin + rcmin <= B) {
            int ldist = Xm-Xl;
            int rdist = Xr-Xm;

            i64 overcost = total_cost - B;
            int reward = lr+rr-hub_count[Xm];

            DBG("overcost", overcost);

            if (ldist < rdist) {
                DBG("RIGHT FIRST");
                if (rdist == 0) while (1) new i64[100000000];

                int to_remove = (overcost+rdist-1) / rdist;
                if (hub_count[Xr] - to_remove < 1) {
                    to_remove = hub_count[Xr]-1;
                }

                overcost -= to_remove * rdist;
                reward -= to_remove;

                if (overcost > 0) {
                    if (ldist == 0) while (1) new i64[100000000];

                    to_remove = (overcost+ldist-1)/ldist;
                    if (hub_count[Xl] - to_remove < 1) while (1) new i64[100000000];

                    overcost -= to_remove * ldist;
                    reward -= to_remove;
                }
            } else {
                DBG("LEFT FIRST");
                if (ldist == 0) while (1) new i64[100000000];

                int to_remove = (overcost+ldist-1) / ldist;
                if (hub_count[Xl] - to_remove < 1) {
                    to_remove = hub_count[Xl]-1;
                }
                DBG(to_remove);

                overcost -= to_remove * ldist;
                reward -= to_remove;
                DBG("overcost 2:", overcost);

                if (overcost > 0) {
                    if (rdist == 0) while (1) new i64[100000000];
                    
                    to_remove = (overcost+rdist-1)/rdist;
                    if (hub_count[Xr] - to_remove < 1) while (1) new i64[100000000];

                    overcost -= to_remove * rdist;
                    reward -= to_remove;
                }
            }

            if (overcost > 0) while (1) new i64[100000000]; // cant happen :)

            if (Xl == 1 && Xr == 4 && Xm == 3) {
                DBG("overcost result:", reward, B + overcost);
            }

            return pair{reward, B + overcost};
        } else {
            return pair{int(), B+1};
        }

    };

    vi Xunique = X;
    Xunique.erase( unique( Xunique.begin(), Xunique.end() ), Xunique.end() );

    vl density(L+1);

    for (int i = 1; i <= L; ++i) {
        density[i] = (i-1) * hub_count;
    }

    int ans = 0;
    for (int i = 0; i < int(Xunique.size()); ++i) {
        int xl = Xunique[i];
        if (lreward[X.back()]-lreward[xl-1] <= ans) break;

        for (int j = i; j < int(Xunique.size()); ++j) {
            int xr = Xunique[j];
            int maxans = lreward[xr]-lreward[xl-1];
            if (maxans <= ans) continue;
            int xm = xl + (density[xr]-density[xl-1]) / maxans;
            DBG("smartpos:", xm, xl, xr);
            for (int x = xm; x <= xm+1 && x <= xr; ++x) {
                auto [reward, cost] = range_query(x, xl, xr);
                if (cost <= B) {
                    if (reward > ans) {
                        DBG("pos:", x, xl, xr);
                        DBG("rice+cost:", reward, cost);
                        ans = reward;
                    }
                }
            }
        }
    }

    return ans;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:172:28: error: no match for 'operator*' (operand types are 'int' and 'vi' {aka 'std::vector<int>'})
  172 |         density[i] = (i-1) * hub_count;
      |                      ~~~~~ ^ ~~~~~~~~~
      |                        |     |
      |                        int   vi {aka std::vector<int>}
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ricehub.cpp:3:
/usr/include/c++/10/complex:391:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const std::complex<_Tp>&)'
  391 |     operator*(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:391:5: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   mismatched types 'const std::complex<_Tp>' and 'int'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ricehub.cpp:3:
/usr/include/c++/10/complex:400:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const _Tp&)'
  400 |     operator*(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:400:5: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   mismatched types 'const std::complex<_Tp>' and 'int'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ricehub.cpp:3:
/usr/include/c++/10/complex:409:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator*(const _Tp&, const std::complex<_Tp>&)'
  409 |     operator*(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:409:5: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   'vi' {aka 'std::vector<int>'} is not derived from 'const std::complex<_Tp>'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from ricehub.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from ricehub.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from ricehub.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const typename _Dom::value_type&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   'vi' {aka 'std::vector<int>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from ricehub.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::valarray<typename _Dom::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from ricehub.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:407:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::valarray<typename _Dom::value_type>&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  407 |     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:407:5: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   'vi' {aka 'std::vector<int>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from ricehub.cpp:3:
/usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const std::valarray<_Tp>&)'
 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1187:1: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   mismatched types 'const std::valarray<_Tp>' and 'int'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from ricehub.cpp:3:
/usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const typename std::valarray<_Tp>::value_type&)'
 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1187:1: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   mismatched types 'const std::valarray<_Tp>' and 'int'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from ricehub.cpp:3:
/usr/include/c++/10/valarray:1187:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__multiplies, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const typename std::valarray<_Tp>::value_type&, const std::valarray<_Tp>&)'
 1187 | _DEFINE_BINARY_OPERATOR(*, __multiplies)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1187:1: note:   template argument deduction/substitution failed:
ricehub.cpp:172:30: note:   'vi' {aka 'std::vector<int>'} is not derived from 'const std::valarray<_Tp>'
  172 |         density[i] = (i-1) * hub_count;
      |                              ^~~~~~~~~