Submission #1169948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169948		M_W_13	Naan (JOI19_naan)	C++20	29 / 100	291 ms	48356 KiB

naan

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    ll T[n][m];
    rep(i, n) {
        rep(j, m) {
            cin >> T[i][j];
        }
    }
    vector<pair<ll, ll>> vec[n];
    rep(i, n) {
        ll suma = 0;
        rep(j, m) {
            suma += T[i][j];
        }
        ll j = 0;
        ll s = 0;
        for (int kt = 1; kt <= n; kt++) {
            while (j < m && ((s + T[i][j]) * n) <= (kt * suma)) {
                s += T[i][j];
                j++;
            }
            if ((s * n) == (kt * suma)) {
                vec[i].pb({j, 1});
                continue;
            }
            ll A = T[i][j];
            ll pot = kt * suma - n * s;
            ll X = j * A * n + pot;
            ll Y = A * n;
            ll dd = __gcd(X, Y);
            X /= dd;
            Y /= dd;
            vec[i].pb({X, Y});
        }
    }
    bool czy[n];
    rep(i, n) {
        czy[i] = false;
    }
    vector<pair<ll, ll>> ans;
    vector<int> perm;
    rep(j, n) {
        pair<ll, ll> p = {m, 1};
        int nr = -1;
        rep(i, n) {
            if (czy[i]) continue;
            if (p.st * vec[i][j].nd >= vec[i][j].st * p.nd) {
                p = vec[i][j];
                nr = i;
            }
        }
        perm.pb(nr + 1);
        czy[nr] = true;
        if (j == n - 1) {
            czy[nr + 1] = true;
            break;
        }
        ans.pb(p);
    }
    rep(i, n - 1) {
        cout << ans[i].st << " " << ans[i].nd << '\n';
    }
    rep(i, n) {
        cout << perm[i] << " ";
    }
    cout << '\n';
    return 0;
}

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