Submission #191342

#	Time	Username	Problem	Language	Result	Execution time	Memory
191342		dolphingarlic	Naan (JOI19_naan)	C++14	100 / 100	1613 ms	116600 KiB

naan

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Rational {
    ll whole, num, den;
    Rational(ll num = 0): whole(num), num(0), den(1) {}
    Rational(ll whole, ll num, ll den): whole(whole), num(num), den(den) {
        norm();
    }

    Rational(ll num, ll den): Rational(0, num, den) {}

    Rational& norm() {
        if (num > den) {
            whole += num / den;
            num %= den;
        }
        ll g = __gcd(num, den);
        num /= g;
        den /= g;
        return *this;
    }
};

bool operator<(const Rational& u, const Rational& v) {
    if (u.whole == v.whole) return u.num * v.den < u.den * v.num;
    return u.whole < v.whole;
}

ostream& operator<<(ostream& cout, const Rational& u) {
    return cout << u.whole * u.den + u.num << ' ' << u.den;
}

Rational cut_places[2001][2001];
bool visited[2001];
int order[2001];
ll a[2001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, l;
    cin >> n >> l;
    FOR(i, 0, n) {
        ll sm = 0;
        FOR(j, 0, l) {
            cin >> a[j];
            sm += a[j];
        }

        ll curr = 0;
        int idx = 0;
        FOR(j, 1, n) {
            while ((curr + a[idx]) * n <= sm * j) curr += a[idx++];
            ll res = sm * j - curr * n;
            cut_places[i][j] = Rational(idx, res, n * a[idx]);
        }
    }

    FOR(i, 1, n) {
        Rational earliest = Rational(1000000000);
        FOR(j, 0, n) if (!visited[j] && cut_places[j][i] < earliest) {
            earliest = cut_places[j][i];
            order[i] = j;
        }
        cout << earliest << '\n';
        visited[order[i]] = true;
    }
    FOR(i, 0, n) if (!visited[i]) order[n] = i;
    FOR(i, 1, n + 1) cout << order[i] + 1 << ' ';
    return 0;
}

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