#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;
| ^~~~~~~~~~~~~~
