Submission #159406

#	Time	Username	Problem	Language	Result	Execution time	Memory
159406		darkkcyan	Naan (JOI19_naan)	C++14	100 / 100	1841 ms	150504 KiB

naan

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

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

struct frac_with_num {
    llong int_part, numerator, denominator;
    frac_with_num(llong num = 0): int_part(num), numerator(0), denominator(1) {}
    frac_with_num(llong whole, llong num, llong den): int_part(whole), numerator(num), denominator(den) {
        norm();
    }

    frac_with_num(llong num, llong den): frac_with_num(0, num, den) {}

    frac_with_num& norm() {
        if (numerator > denominator) {
            int_part += numerator / denominator;
            numerator %= denominator;
        }
        llong g = __gcd(numerator, denominator);
        numerator /= g;
        denominator /= g;
        return *this;
    }
};

bool operator < (const frac_with_num& u, const frac_with_num& v) {
    if (u.int_part == v.int_part) return u.numerator * v.denominator < u.denominator * v.numerator;
    return u.int_part < v.int_part;
}

ostream& operator<<(ostream& cout, const frac_with_num& u) {
    return cout << u.int_part * u.denominator + u.numerator << ' ' << u.denominator;
}


#define maxn 2020
int n, l;
llong v[maxn][maxn];
llong sum[maxn];
vector<frac_with_num> split[maxn];

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> l;
    rep(i, n) {
        sum[i] = 0;
        rep(f, l) {
            cin >> v[i][f];
            sum[i] += v[i][f];
        }
    }

    rep(i, n) {
        llong cur_sum_nan = 0;
        int cur_nan = 0;
        rep1(num_cur_part, n - 1) {
            for (; (cur_sum_nan + v[i][cur_nan]) * n <= sum[i] * num_cur_part; ++cur_nan) 
                cur_sum_nan += v[i][cur_nan];
            llong rest = sum[i] * num_cur_part - cur_sum_nan * n;
            split[i].emplace_back(cur_nan, rest, n * v[i][cur_nan]);
            // clog << cur_nan << ' ' << rest << ' ' << cur_sum_nan << endl;
        }
        split[i].emplace_back(l);

        // clog << i << ": ";
        // for (auto f: split[i]) clog << f << "; ";
        // clog << endl;
    }

    vector<int> ans;
    set<int> has;
    rep(i, n) has.insert(i);

    rep(cur_part, n) {
        auto cur = *min_element(has.begin(), has.end(), [&](int lhs, int rhs) {return split[lhs][cur_part] < split[rhs][cur_part]; } );
        ans.emplace_back(cur);
        has.erase(cur);
        if (cur_part != n - 1) cout << split[cur][cur_part] << '\n';
    }

    
    for (auto i: ans) cout << i + 1 << ' ';


    return 0;
}

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