Submission #1187787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187787		oviyan_gandhi	Naan (JOI19_naan)	C++17	29 / 100	4094 ms	2372 KiB

naan

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

struct Frac {
    int n, d;

    Frac operator + (const Frac &o) const {
        return {n*o.d + o.n*d, d*o.d};
    }

    Frac operator - (const Frac &o) const {
        return {n*o.d - o.n*d, d*o.d};
    }

    bool operator > (const Frac &o) const {
        return n*o.d > o.n*d;
    }

    Frac operator * (const int x) const {
        return { n*x, d };
    }

    Frac operator / (const int x) const {
        return { n, d*x };
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, l; cin >> n >> l;
    vector<vector<int>> v(n, vector<int>(l));
    for (auto &a : v)
        for (int &x : a)
            cin >> x;
    vector<int> ans(n);
    iota(ans.begin(), ans.end(), 0);
    vector<Frac> pts;
    bool possible = false;
    do {
        pts.clear();
        bool cp = true;
        Frac st{0, 1};
        int curr = 0;
        for (int x : ans) {
            Frac req{accumulate(v[x].begin(), v[x].end(), 0), n};
            while (req > ((Frac{curr+1, 1} - st)*v[x][curr])) {
                req = req - ((Frac{curr+1, 1} - st)*v[x][curr]);
                curr++;
                st = {curr, 1};
                if (curr == l) {
                    cp = false;
                    break;
                }
            }
            if (!cp) break;
            st = st + req/v[x][curr];
            pts.push_back(st);
        }
        if (cp) {
            possible = true;
            break;
        }
    } while (next_permutation(ans.begin(), ans.end()));
    if (!possible)
        cout << "-1\n";
    else {
        pts.pop_back();
        for (auto [n, d] : pts)
            cout << n << ' ' << d << '\n';
        for (int x : ans)
            cout << (x+1) << ' ';
        cout << '\n';
    }
    return 0;
}

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