Submission #370451

#	Time	Username	Problem	Language	Result	Execution time	Memory
370451		CodePlatina	Naan (JOI19_naan)	C++17	100 / 100	1030 ms	119736 KiB

naan

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define tlll tuple<long long, long long, long long>
#define tllll tuple<long long, long long, long long, long long>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    int A[n][k];
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < k; ++j)
            cin >> A[i][j];

    vector<plll> ls[n - 1];
    for(int i = 0; i < n; ++i)
    {
        long long s = 0;
        for(int j = 0; j < k; ++j) s += A[i][j];

        int pt = 0;
        long long pf = 0;
        for(int j = 0; j < n - 1; ++j)
        {
            while(pt < k && (pf + A[i][pt]) * n <= s * (j + 1)) pf += A[i][pt++];
            ls[j].push_back({i, { s * (j + 1) - pf * n + 1ll * pt * A[i][pt] * n, A[i][pt] * n }});
        }
    }

    for(int i = 0; i < n - 1; ++i) sort(ls[i].begin(), ls[i].end(), [](plll x, plll y)
    {
        if(x.ee / x.rr != y.ee / y.rr) return x.ee / x.rr < y.ee / y.rr;
        return (x.ee % x.rr) * y.rr < x.rr * (y.ee % y.rr);
    });

//    for(auto i : ls)
//    {
//        for(auto [j, k] : i) cout << j << ' ' << k.ff << ' ' << k.ss << endl;
//        cout << endl;
//    }

    bool chc[n]{};
    int P[n];
    pll ans[n];
    for(int i = 0; i < n - 1; ++i)
    {
        for(int j = 0; j < n; ++j) if(!chc[ls[i][j].ff])
        {
            chc[ls[i][j].ff] = true;
            P[i] = (int)ls[i][j].ff;
            ans[i] = ls[i][j].ss;
            break;
        }
    }
    for(int i = 0; i < n; ++i) if(!chc[i]) P[n - 1] = i;

    for(int i = 0; i < n - 1; ++i) cout << ans[i].ff << ' ' << ans[i].ss << '\n';
    for(int i = 0; i < n; ++i) cout << P[i] + 1 << ' ';
}

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