Submission #1150804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150804		Sharky	Naan (JOI19_naan)	C++20	29 / 100	75 ms	9032 KiB

naan

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()

const int N = 2005;
int v[N][N], ps[N][N], happy[N];
pair<int, int> req[N];

void TLE() {
    TLE();
}

pair<int, int> add(pair<int, int> a, pair<int, int> b) {
    int lc = lcm(a.se, b.se);
    if (a.se == 0 || b.se == 0) TLE();
    a.fi *= (lc / a.se);
    b.fi *= (lc / b.se);
    pair<int, int> res = {a.fi + b.fi, lc};
    int g = gcd(res.fi, res.se);
    if (g) res.fi /= g, res.se /= g;
    return res;
}

pair<int, int> sub(pair<int, int> a, pair<int, int> b) {
    int lc = lcm(a.se, b.se);
    if (a.se == 0 || b.se == 0) TLE();
    a.fi *= (lc / a.se);
    b.fi *= (lc / b.se);
    pair<int, int> res = {a.fi - b.fi, lc};
    int g = gcd(res.fi, res.se);
    if (g) res.fi /= g, res.se /= g;
    return res;
}

pair<int, int> mul(pair<int, int> a, pair<int, int> b) {
    a.fi *= b.fi;
    a.se *= b.se;
    int g = gcd(a.fi, a.se);
    if (g) a.fi /= g, a.se /= g;
    return a;
}

bool leq(pair<int, int> a, pair<int, int> b) { // a <= b
    // debug(a, b);
    return a.fi * b.se <= b.fi * a.se;
}

void solve() {
    int n, len;
    cin >> n >> len;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= len; j++) {
        cin >> v[i][j];
        req[i].fi += v[i][j];
        ps[i][j] = ps[i][j-1] + v[i][j];
    }
    for (int i = 1; i <= n; i++) {
        req[i].se = n;
        int g = gcd(req[i].fi, req[i].se);
        if (g) req[i].fi /= g, req[i].se /= g;
    }
    pair<int, int> pos = {0, 1};
    vector<int> perm;
    vector<pair<int, int>> splits;
    // for (int i = 1; i <= n; i++) debug(req[i]);
    for (int it = 1; it <= n; it++) {
        int id = -1;
        pair<int, int> ep = {1, 0};
        for (int i = 1; i <= n; i++) {
            if (happy[i]) continue;
            int ratio = pos.fi / pos.se;
            if (pos.se == 0) TLE();
            int l = ratio + 1, r = len;
            pair<int, int> diff = sub(make_pair(l, 1), pos);
            diff = mul(diff, make_pair(v[i][l], 1));
            // debug(it, i, diff);
            if (leq(req[i], diff)) {
                pair<int, int> actl = mul(req[i], make_pair(1, v[i][l]));
                actl = add(actl, pos);
                if (leq(actl, ep)) {
                    ep = actl;
                    id = i;
                }
            } else {
                diff = sub(req[i], diff);
                // debug(diff);
                // debug(l, r);
                while (l < r) {
                    int mid = (l + r + 1) / 2;
                    if (leq(make_pair(ps[i][mid] - ps[i][ratio + 1], 1), diff)) l = mid;
                    else r = mid - 1;
                }
                // debug(l, ratio);
                diff = sub(diff, make_pair(ps[i][l] - ps[i][ratio + 1], 1));
                // debug(diff);
                pair<int, int> cur = {l, 1};
                if (l < len) cur = add(cur, mul(diff, make_pair(1, v[i][l+1])));
                if (leq(cur, ep)) {
                    ep = cur;
                    id = i;
                }
                // debug(cur);
            }
        }
        pos = ep;
        // debug(pos);
        if (it < n) cout << pos.first << " " << pos.second << '\n';
        splits.push_back(pos);
        perm.push_back(id);
        happy[id] = 1;
    }
    // for (int i = 0; i < n; i++) cout << splits[i].fi << " \n"[i == n - 1];
    // for (int i = 0; i < n; i++) cout << splits[i].se << " \n"[i == n - 1];
    for (int i = 0; i < n; i++) cout << perm[i] << " \n"[i == n - 1];
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

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