Submission #561940

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
561940	2022-05-13T19:39:12 Z	timreizin	Naan (JOI19_naan)	C++17	Compilation error	0 ms	0 KB

naan

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

using ll = long long;

bool operator<(pair<ll, ll> a, pair<ll, ll> b)
{
    //x/y < z/k
    //xk < zy
    //maybe __int128
    return (__int128)a.first * b.second < (__int128)a.second * b.first;
}

pair<ll, ll> operator-(pair<ll, ll> _a, pair<ll, ll> _b)
{
    pair<__int128, __int128> a(_a.first, _a.second);
    pair<__int128, __int128> b(_b.first, _b.second);
    b.first *= a.second;
    a.first *= b.second;
    pair<__int128, __int128> res{a.first - b.first, a.second * b.second};
    __int128 gcded = gcd(res.first, res.second);
    res.first /= gcded;
    res.second /= gcded;
    return res;
}

pair<ll, ll> operator+(pair<ll, ll> _a, pair<ll, ll> _b)
{
    pair<__int128, __int128> a(_a.first, _a.second);
    pair<__int128, __int128> b(_b.first, _b.second);
    b.first *= a.second;
    a.first *= b.second;
    pair<__int128, __int128> res{a.first + b.first, a.second * b.second};
    __int128 gcded = gcd<__int128>(res.first, res.second);
    res.first /= gcded;
    res.second /= gcded;
    return res;
}


int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, l;
    cin >> n >> l;
    vector<vector<ll>> v(n, vector<ll>(l));
    vector<ll> sum;
    for (auto &i : v)
    {
        for (ll &j : i) cin >> j;
        sum.push_back(accumulate(i.begin(), i.end(), 0ll));
    }
    vector<int> p(n);
    vector<pair<ll, ll>> last(n, {0, 1});
    auto next = [&v, &sum, &n](int i, pair<ll, ll> last) -> pair<ll, ll>
    {
        pair<ll, ll> score{0, 1};
        while (true)
        {
            ll s = v[i][last.first / last.second];
            pair<ll, ll> d = pair{last.first / last.second + 1, 1} - last;
            if (!(pair{d.first * s, d.second} + score < pair{sum[i], n})) break;
            score = score + pair{d.first * s, d.second};
            last = {last.first / last.second + 1, 1};
        }
        //(sum/l - score)/s = d
        pair<ll, ll> d = pair{sum[i], n} - score;
        ll s = v[i][last.first / last.second];
        d.second *= s;
        last = last + d;
        return last;
    };
    for (int i = 0; i < n; ++i)
    {
        int ind = -1;
        for (int j = 0; j < n; ++j)
        {
            if (last[j].second == 0) continue;
            last[j] = next(j, last[j]);
            if (ind == -1 || last[j] < last[ind]) ind = j;
        }
        p[i] = ind + 1;
        if (i != n - 1) cout << last[ind].first << ' ' << last[ind].second << '\n';
        last[ind] = {0, 0};
    }
    for (int i : p) cout << i << ' ';
    return 0;
}

Compilation message

In file included from naan.cpp:3:
/usr/include/c++/10/numeric: In instantiation of 'constexpr std::common_type_t<_Mn, _Nn> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; std::common_type_t<_Mn, _Nn> = __int128]':
naan.cpp:24:47:   required from here
/usr/include/c++/10/numeric:133:21: error: static assertion failed: gcd arguments are integers
  133 |       static_assert(is_integral_v<_Mn>, "gcd arguments are integers");
      |                     ^~~~~~~~~~~~~~~~~~
/usr/include/c++/10/numeric:134:21: error: static assertion failed: gcd arguments are integers
  134 |       static_assert(is_integral_v<_Nn>, "gcd arguments are integers");
      |                     ^~~~~~~~~~~~~~~~~~
/usr/include/c++/10/numeric: In instantiation of 'constexpr std::common_type_t<_Mn, _Nn> std::__detail::__gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; std::common_type_t<_Mn, _Nn> = __int128]':
/usr/include/c++/10/numeric:139:29:   required from 'constexpr std::common_type_t<_Mn, _Nn> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; std::common_type_t<_Mn, _Nn> = __int128]'
naan.cpp:24:47:   required from here
/usr/include/c++/10/numeric:104:49: error: use of deleted function 'void std::__detail::__abs_integral(bool)'
  104 |       return __m == 0 ? __detail::__abs_integral(__n)
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/numeric:98:8: note: declared here
   98 |   void __abs_integral(bool) = delete;
      |        ^~~~~~~~~~~~~~
/usr/include/c++/10/numeric:105:39: error: use of deleted function 'void std::__detail::__abs_integral(bool)'
  105 |  : __n == 0 ? __detail::__abs_integral(__m)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/numeric:98:8: note: declared here
   98 |   void __abs_integral(bool) = delete;
      |        ^~~~~~~~~~~~~~