oj.uz

답안 #332667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332667 2020-12-03T02:34:17 Z 12tqian Naan (JOI19_naan) C++17
0 / 100
 2 ms 512 KB 
#include <bits/stdc++.h>

struct Frac {
    __int128_t n, d;
    Frac(__int128_t _n, __int128_t _d) {
        n = _n, d = _d;
        __int128_t g = std::__gcd(n, d); n /= g, d /= g;
        if (d < 0) n *= -1, d *= -1;
    }
    Frac(__int128_t _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; }
};

int main() {
    using namespace std;
    typedef __int128_t 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++) {
            long long x; cin >> x;
            V[i][j] = x;
        }
    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) {
                Frac add = (1 - at) * V[i][it];
                if (have + add <= need) {
                    have += add;
                    at = 0;
                    it++;
                } else {
                    need = have;
                    at += (need - have) / V[i][it];
                }
            }
            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 << (long long) splits[i].n << " " << (long long) splits[i].d << '\n';
    for (int i = 0; i < N; i++)
        cout << ord[i] + 1 << " ";
    cout << '\n';
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Not a fair distribution.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 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 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 2 ms 492 KB Output is correct
22 Correct 2 ms 492 KB Output is correct
23 Incorrect 0 ms 364 KB Not a fair distribution.
24 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Not a fair distribution.
2 Halted 0 ms 0 KB -