oj.uz

Submission #332651

# Submission time Handle Problem Language Result Execution time Memory
332651 2020-12-03T02:21:53 Z 12tqian Naan (JOI19_naan) C++17
29 / 100
 2183 ms 43200 KB 
#include <bits/stdc++.h>

struct Frac {
    long long n, d;
    Frac(long long _n, long long _d) {
        n = _n, d = _d;
        long long g = std::__gcd(n, d); n /= g, d /= g;
        if (d < 0) n *= -1, d *= -1;
    }
    Frac(long long _n) : Frac(_n, 1) {}
    Frac() : Frac(0) {}
    friend Frac abs(Frac F) { return Frac(abs(F.n), F.d); }
    friend bool operator < (const Frac& l, const Frac& r) { return l.n * r.d < r.n * l.d; }
    friend bool operator <= (const Frac& l, const Frac& r) { return l.n * r.d <= r.n * l.d; }
    friend bool operator > (const Frac& l, const Frac& r) { return l.n * r.d > r.n * l.d; }
    friend bool operator >= (const Frac& l, const Frac& r) { return l.n * r.d >= r.n * l.d; }
    friend bool operator == (const Frac& l, const Frac& r) { return l.n == r.n && l.d == r.d; }
    friend bool operator != (const Frac& l, const Frac& r) { return !(l == r); }
    Frac operator - () const { return Frac(-n, d); }
    friend Frac operator + (const Frac& l, const Frac& r) { return Frac(l.n * r.d + r.n * l.d, l.d * r.d); }
    friend Frac operator - (const Frac& l, const Frac& r) { return Frac(l.n * r.d - r.n * l.d, l.d * r.d); }
    friend Frac operator * (const Frac& l, const Frac& r) { return Frac(l.n * r.n, l.d * r.d); }
    friend Frac operator * (const Frac& l, int r) { return l * Frac(r, 1); }
    friend Frac operator * (int r, const Frac& l) { return l * r; }
    friend Frac operator / (const Frac& l, const Frac& r) { return l * Frac(r.d, r.n); }
    friend Frac operator / (const Frac& l, const int& r) { return l / Frac(r, 1); }
    friend Frac operator / (const int& l, const Frac& r) { return Frac(l, 1) / r; }
    friend Frac& operator += (Frac& l, const Frac& r) { return l = l + r; }
    friend Frac& operator -= (Frac& l, const Frac& r) { return l = l - r; }
    template <class T> friend Frac& operator *= (Frac& l, const T& r) { return l = l * r; }
    template <class T> friend Frac& operator /= (Frac& l, const T& r) { return l = l / r; }
    friend std::ostream& operator << (std::ostream& os, const Frac& a) { return os << a.n << "/" << a.d; }
};

int main() {
    using namespace std;
    typedef long long ll;
    ios_base::sync_with_stdio(0);
    int N, L; 
    cin >> N >> L;
    vector<vector<ll>> V(N, vector<ll>(L));
    for (int i = 0; i < N; i++) 
        for (int j = 0; j < L; j++)
            cin >> V[i][j];
    vector<vector<Frac>> split(N, vector<Frac>(N + 1));
    for (int i = 0; i < N; i++) {
        Frac need = 0;
        for (int j = 0; j < L; j++)
            need += V[i][j];
        need /= N;
        split[i][0] = 0;
        Frac have = 0;
        int it = 0;
        Frac at = 0;
        for (int j = 1; j <= N; j++) {
            while (have < need) {
                if (have + (1 - at) * V[i][it] <= need) {
                    have += (1 - at) * V[i][it];
                    at = 0;
                    it++;
                } else {
                    Frac go = (need - have) / V[i][it];
                    have += go * V[i][it];
                    at += go;
                }
            }
            split[i][j] = it + at;
            have = 0;
        }
    }
    const int INF = 1e9;
    vector<Frac> splits(N);
    vector<int> ord(N);
    vector<bool> used(N);
    for (int i = 1; i <= N - 1; i++) {
        pair<Frac, int> best = {INF, INF};
        for (int j = 0; j < N; j++) 
            if (!used[j])
                best = min(best, {split[j][i], j});
        splits[i - 1] = best.first;
        ord[i - 1] = best.second;
        used[best.second] = true;
    }
    for (int i = 0; i < N; i++) {
        if (!used[i])
            ord.back() = i;
    }
    for (int i = 0; i < N - 1; i++)
        cout << splits[i].n << " " << splits[i].d << '\n', assert(splits[i].n > 0 && splits[i].d > 0);
    for (int i = 0; i < N; i++)
        cout << ord[i] + 1 << " ";
    cout << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 3 ms 492 KB Output is correct
19 Correct 3 ms 492 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 3 ms 492 KB Output is correct
22 Correct 3 ms 492 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 3 ms 364 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 3 ms 492 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 2 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 2 ms 364 KB Output is correct
29 Correct 2 ms 364 KB Output is correct
30 Correct 2 ms 364 KB Output is correct
31 Correct 2 ms 492 KB Output is correct
32 Correct 2 ms 364 KB Output is correct
33 Correct 3 ms 492 KB Output is correct
34 Correct 3 ms 492 KB Output is correct
35 Correct 2 ms 364 KB Output is correct
36 Correct 3 ms 492 KB Output is correct
37 Correct 3 ms 492 KB Output is correct
38 Correct 1 ms 364 KB Output is correct
39 Correct 2 ms 364 KB Output is correct
40 Correct 2 ms 364 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 3 ms 364 KB Output is correct
43 Correct 354 ms 7604 KB Output is correct
44 Incorrect 2183 ms 43200 KB X_i is not increasing
45 Halted 0 ms 0 KB -