Submission #749198

#	Time	Username	Problem	Language	Result	Execution time	Memory
749198		piOOE	Naan (JOI19_naan)	C++17	100 / 100	402 ms	100908 KiB

naan

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Frac {
    ll num = 0, den = 1;

    Frac() = default;
    Frac(ll a, ll b) : num(a), den(b) {}

    bool operator<(const Frac &oth) const {
        ll a = num / den, b = oth.num / oth.den;
        return pair{a, oth.den * (num - den * a)} < pair{b, den * (oth.num - oth.den * b)};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, L;
    cin >> n >> L;

    vector v(n, vector<int>(L));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < L; ++j) {
            cin >> v[i][j];
        }
    }

    vector p(n, vector<Frac>(n));

    for (int i = 0; i < n; ++i) {
        ll sum = accumulate(v[i].begin(), v[i].end(), 0LL);
        ll pref = 0;
        Frac last{};

        for (int j = 0, k = 0; j < n; ++j) {
            while (k < L && pref * n < sum * (j + 1)) {
                pref += v[i][k++];
            }

            if (Frac(k, 1) < last) {
                last.num += sum;
            } else {
                last = Frac(1LL * n * v[i][k - 1] * (k - 1) + sum * (j + 1) - n * (pref - v[i][k - 1]), n * v[i][k - 1]);
            }

            p[i][j] = last;
        }
    }

    vector<bool> used(n);
    vector<int> ord;

    for (int j = 0; j < n; ++j) {
        Frac best(1e9, 1);
        int b = -1;

        for (int i = 0; i < n; ++i) {
            if (!used[i] && p[i][j] < best) {
                best = p[i][j];
                b = i;
            }
        }

        if (j + 1 < n) {
            cout << best.num << " " << best.den << '\n';
        }
        ord.push_back(b);
        used[b] = true;
    }

    for (int x : ord) {
        cout << x + 1 << ' ';
    }

    cout << '\n';

    return 0;
}

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