oj.uz

답안 #1027493

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1027493 2024-07-19T07:04:41 Z vjudge1 Naan (JOI19_naan) C++17
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct fraction {
    ll a;
    ll b;
    fraction (ll x = 0) : a(x), b(1) {}
    fraction (ll a, ll b) : a(a), b(b) {}
};
fraction operator + (fraction f, fraction g) {
    fraction res;
    res.a = f.a * g.b + g.a * f.b;
    res.b = f.b * g.b;
    assert(res.b <= 1e9);
    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;
    assert(res.b <= 1e9);
    return res;
}
fraction operator * (fraction f, fraction g) {
    fraction res;
    res.a = f.a * g.a;
    res.b = f.b * g.b;
    return res;
}
fraction operator / (fraction f, fraction g) {
    fraction res;
    res.a = f.a * g.b;
    res.b = f.b * g.a;
    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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 600 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -