Submission #244771

#	Time	Username	Problem	Language	Result	Execution time	Memory
244771		thecodingwizard	Naan (JOI19_naan)	C++11	29 / 100	1725 ms	53112 KiB

naan

#include <bits/stdc++.h>

using namespace std;

#define ll long long

// returns true if fraction a < fraction b
bool better(pair<ll, ll> a, pair<ll, ll> b) {
    return a.first*b.second<a.second*b.first;
}

int main() {
    int n, l; cin >> n >> l;
    ll V[n][l];
    ll sum[n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < l; j++) cin >> V[i][j];
        sum[i] = 0; for (int j = 0; j < l; j++) sum[i] += V[i][j];
    }
    pair<ll, ll> split[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            ll want = sum[i]*j;
            int cur = 0;
            while (cur < l && V[i][cur]*n <= want) {
                want -= V[i][cur]*n;
                cur++;
            }
            split[i][j] = make_pair(cur*V[i][cur]*n+want, V[i][cur]*n);
            //cout << "split[" << i << "][" << j << "] = " << split[i][j].first << "/" << split[i][j].second << endl;
        }
    }
    bool taken[n]; for (int i = 0; i < n; i++) taken[i] = false;
    vector<int> permutation;
    for (int i = 1; i < n; i++) {
        int best = -1;
        for (int j = 0; j < n; j++) {
            if (taken[j]) continue;
            if (best == -1) {
                best = j;
            } else {
                if (better(split[j][i], split[best][i])) best = j;
            }
        }
        taken[best] = true;
        cout << split[best][i].first << " " << split[best][i].second << endl;
        permutation.push_back(best+1);
    }
    for (int j = 0; j < n; j++) if (!taken[j]) permutation.push_back(j+1);
    for (int x : permutation) cout << x << " ";
    cout << endl;
    return 0;
}

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