Submission #1027498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027498		vjudge1	Naan (JOI19_naan)	C++17	24 / 100	3 ms	604 KiB

naan

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
    if (!b) return a;
    return gcd(b, a % b);
}

struct fraction {
    ll a;
    ll b;
    fraction (ll x = 0) : a(x), b(1) {}
    fraction (ll a, ll b) : a(a), b(b) {}
    void norm() {
        ll g = gcd(a, b);
        a /= g, b /= g;
    }
};

fraction operator + (fraction f, fraction g) {
    fraction res;
    res.a = f.a * g.b + g.a * f.b;
    res.b = f.b * g.b;
    if (res.b > 1e9) res.norm();
    return res;
}
fraction operator - (fraction f, fraction g) {
    fraction res;
    res.a = f.a * g.b - g.a * f.b;
    res.b = f.b * g.b;
    if (res.b > 1e9) res.norm();
    return res;
}
fraction operator * (fraction f, fraction g) {
    fraction res;
    res.a = f.a * g.a;
    res.b = f.b * g.b;
    if (res.b > 1e9) res.norm();
    return res;
}
fraction operator / (fraction f, fraction g) {
    fraction res;
    res.a = f.a * g.b;
    res.b = f.b * g.a;
    if (res.b > 1e9) res.norm();
    return res;
}
ostream& operator << (ostream& out, const fraction &a) {
    out << a.a << '/' << a.b;
    return out;
}

bool operator < (fraction f, fraction g) { return (f.a * g.b < g.a * f.b); }
bool operator > (fraction f, fraction g) { return (f.a * g.b < g.a * f.b); }
bool operator <= (fraction f, fraction g) { return !(f > g); }
bool operator >= (fraction f, fraction g) { return !(f < g); }

const int N = 1010;

int n, L;
int v[N][N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> L;
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= L; j++)
            cin >> v[i][j];


    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    auto p0 = p;
    do {
        // for (int c : p) cout << c << ' ';
        // cout << '\n';

        fraction r[n];
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= L; j++)
                r[i] = r[i] + v[i][j];
            r[i].b = n;
        }        
        vector<fraction> div;
        int cur = 0, i = 1;
        while (cur < n && i <= L) {
            int w = v[p[cur]][i];
            fraction pr = ((div.empty() || div.back() < i - 1) ? i - 1 : div.back());
 
            if ((i - pr) * w >= r[p[cur]]) {
                div.push_back(r[p[cur]] / w + pr);
                r[p[cur]] = 0;
                cur++;
            } else {
                r[p[cur]] = r[p[cur]] - (i - pr) * w;
                i++;
            }
            // for (int j = 0; j < 2; j++) 
            //     cout << r[j] << ' ';
            // cout << '\n';
        }

        if (cur == n) {
            for (int i = 0; i < n - 1; i++) 
                cout << div[i].a << ' ' << div[i].b << '\n';
            for (int i = 0; i < n; i++)
                cout << p[i] + 1 << ' ';
            return 0;
        }
        next_permutation(p.begin(), p.end());
    } while (p != p0);


    cout << -1;
}

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