Submission #1151081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151081		Sharky	Naan (JOI19_naan)	C++20	100 / 100	1503 ms	126060 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], req[N], ps[N][N], happy[N];
pair<int, int> s[N][N];

pair<int, int> add(pair<int, int> a, pair<int, int> b) {
    int lc = lcm(a.se, b.se);
    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);
    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) {
    return (__int128) a.fi * b.se <= (__int128) a.se * b.fi;
}

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] += v[i][j];
            ps[i][j] = ps[i][j-1] + v[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int it = 1; it <= n; it++) {
            pair<int, int> p = {it * req[i], n};
            int l = 0, r = len;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (leq(make_pair(ps[i][mid], 1), p)) l = mid;
                else r = mid - 1;
            }
            if (l < len) {
                pair<int, int> diff = sub(p, make_pair(ps[i][l], 1));
                pair<int, int> cur = add(make_pair(l, 1), mul(diff, make_pair(1, v[i][l+1])));
                s[i][it] = cur;
            } else s[i][it] = {len, 1};
        }
    }
    vector<int> perm;
    for (int it = 1; it <= n; it++) {
        pair<int, int> ep = {1, 0};
        int id;
        for (int i = 1; i <= n; i++) {
            if (happy[i]) continue;
            if (leq(s[i][it], ep)) ep = s[i][it], id = i;
        }
        perm.push_back(id);
        happy[id] = 1;
        if (it < n) cout << ep.first << " " << ep.second << '\n';
    }
    for (int e : perm) cout << e << ' ';
}

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: 71 / 71