oj.uz

Submission #244753

# Submission time Handle Problem Language Result Execution time Memory
244753 2020-07-04T21:59:50 Z thecodingwizard Naan (JOI19_naan) C++11
0 / 100
 5 ms 384 KB 
#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);
    cout << l << " 1" << endl;
    for (int x : permutation) cout << x << " ";
    cout << endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Integer parameter [name=P_i] equals to 5, violates the range [1, 2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Integer parameter [name=P_i] equals to 1168, violates the range [1, 2]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Integer parameter [name=P_i] equals to 5, violates the range [1, 2]
2 Halted 0 ms 0 KB -