| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 561940 | timreizin | Naan (JOI19_naan) | C++17 | 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.
#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;
}