Submission #1170476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170476		patgra	Naan (JOI19_naan)	C++20	29 / 100	698 ms	81544 KiB

naan

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

struct frac {
    ll num, den;
};
frac skroc(frac x) {
    auto g = gcd(x.num, x.den);
    return {x.num / g, x.den / g};
}
bool cmp(pair<frac, int> x, pair<frac, int> y) {
    auto a = x.first, b = y.first;
    return ((__int128)a.num) * b.den < ((__int128)b.num) * a.den;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, l;
    cin >> n >> l;
    vector<vector<ll>> arr(n, vector<ll>(l));
    vector<ll> whole(n, 0);
    rep(i, 0, n) rep(j, 0, l) cin >> arr[i][j], whole[i] += arr[i][j];
    vector<vector<frac>> breakPoints(n, vector<frac>(n));
    rep(i, 0, n) {
        frac lookedFor = {whole[i], n};
        int it = 0;
        ll prefSum = 0;
        rep(j, 0, n - 1) {
            lookedFor.num *= j + 1;
            while(it < l && (prefSum + arr[i][it]) * lookedFor.den <= lookedFor.num) prefSum += arr[i][it++];
            frac funFrac = {lookedFor.num - prefSum * lookedFor.den, lookedFor.den};
            funFrac.den *= arr[i][it];
            funFrac.num += funFrac.den * it;
            breakPoints[i][j] = skroc(funFrac);
            DC << "BP[" << i << "][" << j << "] = " << breakPoints[i][j].num << " / " << breakPoints[i][j].den << eol;
            DC << ' ' << it << "  " << lookedFor.num << ' ' << lookedFor.den << eol;
            lookedFor.num /= j + 1;
        }
    }
    vector<bool> done(n, false);
    vector<int> perm(n);
    frac prv = {0, 1};
    rep(i, 0, n - 1) {
        vector<pair<frac, int>> V;
        rep(j, 0, n) if(!done[j]) V.pb({breakPoints[j][i], j});
        ranges::sort(V, cmp);
        auto [f, j] = V[0];
        assert(f.den <= 1000000000ll);
        assert(prv.num * f.den < f.num * prv.den);
        prv = f;
        cout << f.num << ' ' << f.den << '\n';
        perm[i] = j;
        done[j] = true;
    }
    rep(i, 0, n) if(!done[i]) perm[n - 1] = i;
    repIn(i, perm) cout << i + 1 << ' ';
    cout << '\n';
}

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