Submission #1175475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175475		OI_Account	Naan (JOI19_naan)	C++20	0 / 100	0 ms	324 KiB

naan

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

#define X first
#define Y second

typedef long long ll;
typedef __int128 l2;
typedef pair<ll, ll> point;

const int N = 2000;

int n, l, ans[N + 10];
ll a[N + 10][N + 10];
point p[N + 10][N + 10];
bool mark[N + 10];

void readInput() {
    cin >> n >> l;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= l; j++) {
            cin >> a[i][j];
            a[i][j] *= (ll) n;
        }
}

void calcP(int i) {
    ll all = 0;
    for (int j = 1; j <= l; j++)
        all += a[i][j];
    int pnt = l;
    ll sum = 0;
    for (int j = 1; j < n; j++) {
        ll need = (all / (ll) n) * j;
        while (sum + a[i][pnt] < need) {
            sum += a[i][pnt];
            pnt--;
        }
        p[i][j] = {need - sum, a[i][pnt]};
        p[i][j].X += (ll) (l - pnt) * p[i][j].Y;
    }
}

void calcP() {
    for (int i = 1; i <= n; i++)
        calcP(i);
}

point maxP(point a, point b) {
    l2 lft = (l2) a.X * b.Y;
    l2 rght = (l2) b.X * a.Y;
    return lft < rght? b: a;
}

int getMax(int i, int j, int t) {
    return maxP(p[i][t], p[j][t]) == p[i][t]? i: j;
}

void calcAns() {
    fill(mark + 1, mark + n + 1, true);
    for (int i = n - 1; i >= 1; i--) {
        int tmp = 0;
        for (int j = 1; j <= n; j++)
            if (mark[j])
                tmp = (tmp? getMax(tmp, j, i): j);
        cout << p[tmp][i].X << ' ' << p[tmp][i].Y << '\n';
        mark[tmp] = false;
        ans[n - i] = tmp;
    }
    int idx = 0;
    for (int i = 1; i <= n; i++)
        if (mark[i])
            idx = i;
    ans[n] = idx;
}

void writeOutput() {
    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcP();
    calcAns();
    writeOutput();
    return 0;
}

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