Submission #561943

#	Time	Username	Problem	Language	Result	Execution time	Memory
561943		timreizin	Naan (JOI19_naan)	C++17	100 / 100	1285 ms	54004 KiB

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;
}

__int128 gcd(__int128 a, __int128 b)
{
    if (a < b) swap(a, b);
    while (b != 0)
    {
        a %= b;
        swap(a, b);
    }
    return a;
}

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(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;
}

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 71 / 71