oj.uz

Submission #1027689

# Submission time Handle Problem Language Result Execution time Memory
1027689 2024-07-19T09:08:22 Z vjudge1 Naan (JOI19_naan) C++17
24 / 100
 11 ms 604 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Incorrect 0 ms 348 KB Not a fair distribution.
11 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 516 KB Output is correct
10 Correct 1 ms 508 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 488 KB Output is correct
14 Correct 4 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 11 ms 348 KB Output is correct
19 Correct 5 ms 604 KB Output is correct
20 Correct 1 ms 476 KB Output is correct
21 Correct 1 ms 504 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Incorrect 0 ms 348 KB Not a fair distribution.
11 Halted 0 ms 0 KB -