제출 #1027689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1027689		vjudge1	Naan (JOI19_naan)	C++17	24 / 100	11 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;
    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;
    res.norm();
    return res;
}
fraction operator * (fraction f, fraction g) {
    fraction res;
    res.a = f.a * g.a;
    res.b = f.b * g.b;
    res.norm();
    return res;
}
fraction operator / (fraction f, fraction g) {
    fraction res;
    res.a = f.a * g.b;
    res.b = f.b * g.a;
    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;
            r[i].norm();
        }
        if (n == 2) {
            ll s = 0;
            int i = 1;
            while (i <= L && (s + v[p[0]][i]) <= r[p[0]]) {
                s += v[p[0]][i++];
            }
            if (i > L) continue;
            fraction t = (r[p[0]] - s) / v[p[0]][i] + (i - 1);
            fraction rs = (i - t) * v[p[1]][i];
            while (i < L) {
                i++;
                rs = rs + v[p[1]][i];
            }
            if (rs >= r[p[1]]) {
                cout << t.a << ' ' << t.b << '\n';
                for (int i = 0; i < n; i++)
                    cout << p[i] + 1 << ' ';
                return 0;
            }
            next_permutation(p.begin(), p.end());
            continue;
        }

        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