Submission #1125688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125688		OI_Account	Naan (JOI19_naan)	C++20	29 / 100	78 ms	13228 KiB

naan

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

#define big __int128

const int N = 2000;
const big INF = 1'000'000'000;

big gcd(big a, big b) {
    return b? gcd(b, a % b): a;
}

int n, len, mark[N + 10];
big a[N + 10][N + 10];
big sum[N + 10][N + 10];
vector<int> ans;

void readInput() {
    cin >> n >> len;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= len; j++) {
            long long x;
            cin >> x;
            a[i][j] = x * (big) n;
            sum[i][j] = sum[i][j - 1] + a[i][j];
        }
}

struct kasr {
    big a, b;
    void cmp() {
        big g = gcd(llabs(a), llabs(b));
        a /= g;
        b /= g;
        /*if (b > INF) {
            big res = (big) ((big) a * (big) INF + (big) (b - 1)) / (big) b;
            a = res;
            b = INF;
        }*/
        g = gcd(llabs(a), llabs(b));
        a /= g;
        b /= g;
    }
};

kasr pnt;
kasr mKasr(big x, big y) {
    kasr res;
    res.a = x;
    res.b = y;
    res.cmp();
    return res;
}

kasr mKasr(big x) {
    kasr res;
    res.a = x;
    res.b = 1;
    res.cmp();
    return res;
}  

big getVal(kasr x) {
    return x.a / x.b + 1;
}

kasr operator+(const kasr &x, const kasr &y) {
    return mKasr(x.a * y.b + y.a * x.b, x.b * y.b);
}

kasr operator*(const kasr &x, const kasr &y) {
    return mKasr(x.a * y.a, x.b * y.b);
}

kasr operator/(const kasr &x, const kasr &y) {
    return mKasr(x.a * y.b, x.b * y.a);
}

kasr operator-(const kasr &x, const kasr &y) {
    return mKasr(x.a * y.b - y.a * x.b, x.b * y.b);
}

bool operator<(const kasr &x, const kasr &y) {
    return x.a * y.b < y.a * x.b;
}

vector<kasr> res;

kasr calcSum(int idx, int mid) {
    int x = getVal(pnt);
    kasr here = mKasr(a[idx][x]) * (mKasr(x) - pnt);
    return mKasr(sum[idx][mid] - sum[idx][x]) + here;
}

kasr calcNext(int idx) {
    kasr need = mKasr(sum[idx][len]) / mKasr(n);
    int l = getVal(pnt) - 1, r = len + 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (calcSum(idx, mid) < need)
            l = mid;
        else
            r = mid;
    }
    /*if (r == len + 1)
        return mKasr(-1);*/
    int x = getVal(pnt);
    kasr remain = (r == x? need: need - calcSum(idx, r - 1));
    kasr last = (r == x? pnt: mKasr(r - 1));
    //cout << idx << ": " << r << ' ' << calcSum(idx, 1).a << ' ' << calcSum(idx, 1).b << ' ' << (calcSum(idx, 1) < need) << endl;
    return last + remain / mKasr(a[idx][r]);
}

void add() {
    //cout << "add " << endl;
    int idx = 0;
    kasr newPnt;
    for (int i = 1; i <= n; i++)
        if (!mark[i]) {
            kasr tmp = calcNext(i);
            if (tmp.a != -1 && (idx == 0 || tmp < newPnt)) {
                idx = i;
                newPnt = tmp;
            }
        }
    if (!idx)
        return;
    newPnt.cmp();
    mark[idx] = true;
    ans.push_back(idx);
    res.push_back(newPnt);
    pnt = newPnt;
}

void solve() {
    pnt = mKasr(0, 1);
    for (int i = 1; i <= n; i++)
        add();
}

void writeOutput() {
    if (ans.size() != n) {
        cout << -1 << flush;
        return;
    }
    for (int i = 0; i < n - 1; i++)
        cout << (long long) res[i].a << ' ' << (long long) res[i].b << '\n';
    for (auto id: ans)
        cout << id << ' ';
    cout.flush();
}

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

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