Submission #1129295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129295		antonn	Naan (JOI19_naan)	C++20	29 / 100	23 ms	5700 KiB

naan

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


int n, L;
vector<vector<int>> v;
vector<vector<__int128>> pref;


mt19937 rng((long long) (new char));


struct Frac {
    __int128 p;
    __int128 q;

    Frac(__int128 a = 0, __int128 b = 1) : p(a), q(b) {}

    void reduce() {
        __int128 d = __gcd(p, q);
        p /= d;
        q /= d;
    }

    ll getIntValue() {
        return p / q;
    }
};


bool operator <= (Frac a, Frac b) {
    return a.p * b.q <= a.q * b.p;
}


__int128 lcm(__int128 a, __int128 b) {
    return a * b / __gcd(a, b);
}


void myassert(bool cond) {
    if (cond == false) {
        while (true);
    }
}


Frac operator + (Frac a, Frac b) {
    Frac c = {0, 0};
    __int128 d = lcm(a.q, b.q);
    myassert(d >= 0);
    c.p = a.p * (d / a.q) + b.p * (d / b.q);
    c.q = d;
    return c;
}


Frac operator - (Frac a, Frac b) { 
    assert(b <= a);
    Frac c;
    __int128 d = lcm(a.q, b.q);
    myassert(d >= 0);
    c.p = a.p * (d / a.q) - b.p * (d / b.q);
    c.q = d;
    return c;
}


Frac operator * (int x, Frac f) {
    Frac res = {f.p * x, f.q};
    res.reduce();
    return res;
}


Frac operator / (Frac f, int x) {
    Frac res = {f.p, f.q * x};
    res.reduce();
    return res;
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> L;
    v.assign(n + 1, vector<int>(L + 2));
    pref.assign(n + 1, vector<__int128>(L + 1));
    vector<Frac> need(n + 1);
    for (int i = 1; i <= n; i += 1) {
        ll sum = 0;
        for (int j = 1; j <= L; j += 1) {
            cin >> v[i][j];
            sum += v[i][j];
            pref[i][j] = pref[i][j - 1] + v[i][j];
        }
        v[i][L + 1] = 1;
        need[i] = {sum, n};
        need[i].reduce();
    }
    vector<pair<int, Frac>> sol;
    for (int step = 1; step <= 100; step += 1) {
        vector<int> ord(n);
        iota(all(ord), 1);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);

        vector<pair<int, Frac>> cur;
        Frac eaten = {0, 1};
        int full = 0;
        bool bad = 0;
        for (auto i : ord) {
            Frac split;
            if (full == L) {
                bad = 1;
                break;
            }
            if (need[i] <= v[i][full + 1] * (Frac(full + 1, 1) - eaten)) {
                split = eaten + (need[i] / v[i][full + 1]);
                split.reduce();
            } else {
                Frac aux = need[i];
                aux = aux - v[i][full + 1] * (Frac(full + 1, 1) - eaten);
                split.reduce();
                assert(Frac(0, 1) <= aux);
                int low = full + 2, high = L, sol = full + 1;
                while (low <= high) {
                    int m = (low + high) / 2;
                    if (Frac(pref[i][m] - pref[i][full + 1], 1) <= aux) {
                        sol = m;
                        low = m + 1;
                    } else {
                        high = m - 1;
                    }
                }
                if (sol > L) {
                    bad = 1;
                    break;
                }
                aux = aux - Frac(pref[i][sol] - pref[i][full + 1], 1);
                split = sol + (aux / v[i][sol + 1]);
                split.reduce();
                if (!(split <= Frac(L, 1))) {
                    bad = 1;
                    break;
                }
            }
            eaten = split;
            full = eaten.getIntValue();
            cur.push_back({i, eaten});
        }
        if (bad == 0) {
            sol = cur;
            break;
        }
    }
    if (sol.size() != n) {
        cout << -1 << "\n";
        return 0;
    }
    
    for (int i = 0; i < sol.size() - 1; i += 1) {
        int who = sol[i].first;
        Frac split = sol[i].second;
        cout << (ll) split.p << " " << (ll) split.q << "\n";
    }
    for (int i = 0; i < sol.size(); i += 1) {
        int who = sol[i].first;
        Frac split = sol[i].second;
        cout << who << " ";
    }
    cout << "\n";
    return 0;
}

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