Submission #1129321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129321		antonn	Naan (JOI19_naan)	C++20	100 / 100	1422 ms	144760 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<ll>> pref;

struct Frac {
    __int128 p;
    __int128 q;

    Frac(ll a = 0, ll b = 1) : p(a), q(b) {}
    
    void reduct() {
        ll d = __gcd(p, q);
        p /= d;
        q /= d;
    }
};


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


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


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


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


Frac operator - (ll x, Frac f) {
    return {x * f.q - f.p, f.q};
}


Frac operator - (Frac f, ll x) {
    return {f.p - x * f.q, f.q};
}


Frac operator * (Frac f, ll x) {
    f.p *= x;
    return f;
}


Frac operator / (Frac f, ll x) {
    f.q *= x;
    return f;
}


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));
    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];
        }
        v[i][L + 1] = 1;
        need[i] = {sum, n};
    }
    vector<vector<Frac>> cuts(n + 1);
    for (int i = 1; i <= n; i += 1) {
        Frac pos = {0, 1};
        Frac c = {0, 1};
        Frac sum = {0, 1};
        int full = 0;
        cuts[i].push_back({0, 1});
        while (full != L) {
            if (sum + (full + 1 - c) * v[i][full + 1] <= need[i]) {
                sum = sum + (full + 1 - c) * v[i][full + 1];
                full += 1;
                c = {full, 1};
            } else {
                c = c + (need[i] - sum) / v[i][full + 1];
                c.reduct();
                cuts[i].push_back(c);
                assert(c.p != 0);
                sum = {0, 1};
            }
        }
        assert(cuts[i].size() == n);
        cuts[i].push_back({L, 1});
    }
    vector<int> rem(n);
    iota(all(rem), 1);
    vector<pair<int, Frac>> sol;
    Frac last = {-1, 1};
    for (int it = 1; it <= n; it += 1) {
        pair<int, Frac> best = {-1, {L, 1}};
        for (int i : rem) {
            int low = 0, high = n - 1, sol = -1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (last <= cuts[i][mid]) {
                    sol = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            if (sol != -1) {
                if (cuts[i][sol + 1] <= best.second) {
                    assert(i != 0 && sol != -1);
                    best = {i, cuts[i][sol + 1]};
                }
            }
        }
        if (best.first == -1) {
            cout << -1 << "\n";
            return 0;
        }
        sol.push_back(best);
        vector<int> nw;
        for (auto i : rem) {
            if (i != best.first) {
                nw.push_back(i);
            }
        }
        rem = nw;
        last = best.second;
    }
    for (int i = 0; i < sol.size() - 1; i += 1) {
        int who = sol[i].first;
        Frac split = sol[i].second;
        // assert(split.p != 0);
        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;
}

Compilation message (stderr)

naan.cpp: In function 'Frac operator-(long long int, Frac)':
naan.cpp:58:21: warning: narrowing conversion of '((((__int128)x) * f.Frac::q) - f.Frac::p)' from '__int128' to 'long long int' [-Wnarrowing]
   58 |     return {x * f.q - f.p, f.q};
      |             ~~~~~~~~^~~~~
naan.cpp:58:30: warning: narrowing conversion of 'f.Frac::q' from '__int128' to 'long long int' [-Wnarrowing]
   58 |     return {x * f.q - f.p, f.q};
      |                            ~~^
naan.cpp: In function 'Frac operator-(Frac, long long int)':
naan.cpp:63:17: warning: narrowing conversion of '(f.Frac::p - (((__int128)x) * f.Frac::q))' from '__int128' to 'long long int' [-Wnarrowing]
   63 |     return {f.p - x * f.q, f.q};
      |             ~~~~^~~~~~~~~
naan.cpp:63:30: warning: narrowing conversion of 'f.Frac::q' from '__int128' to 'long long int' [-Wnarrowing]
   63 |     return {f.p - x * f.q, f.q};
      |                            ~~^

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