oj.uz

Submission #702418

# Submission time Handle Problem Language Result Execution time Memory
702418 2023-02-24T03:55:54 Z PixelCat Naan (JOI19_naan) C++14
29 / 100
 3 ms 724 KB 
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

struct Frac {
    int x, y;
    Frac(int _x = 0, int _y = 1) {
        x = _x; y = _y;
        simp();
    }
    void simp() {
        int g = __gcd(x, y);
        x /= g; y /= g;
    }
};
Frac operator-(const Frac &a) {
    return Frac(-a.x, a.y);
}
Frac operator+(const Frac &a, const Frac &b) {
    return Frac(a.x * b.y + a.y * b.x, a.y * b.y);
}
Frac operator-(const Frac &a, const Frac &b) {
    return a + (-b);
}
Frac operator*(const Frac &a, const Frac &b) {
    return Frac(a.x * b.x, a.y * b.y);
}
Frac operator/(const Frac &a, const Frac &b) {
    return Frac(a.x * b.y, a.y * b.x);
}
bool operator==(const Frac &a, const Frac &b) {
    return a.x * b.y == a.y * b.x;
}
bool operator<(const Frac &a, const Frac &b) {
    return a.x * b.y < a.y * b.x;
}
bool operator>(const Frac &a, const Frac &b) {
    return b < a;
}
bool operator<=(const Frac &a, const Frac &b) {
    return a < b || a == b;
}
bool operator>=(const Frac &a, const Frac &b) {
    return a > b || a == b;
}

const int MAXN = 2010;

int v[MAXN][MAXN];
Frac tar[MAXN];
int ids[MAXN];
Frac rem[MAXN];
Frac x[MAXN];

bool check(int n, int l) {
    For(i, 1, l) rem[i] = Frac(1);
    int pos = 1;
    For(it, 1, n) {
        int id = ids[it];
        Frac now(0);
        while(now + rem[pos] * v[id][pos] < tar[id]) {
            if(pos == l) return false;
            now = now + rem[pos] * v[id][pos];
            pos++;
        }
        Frac owo = (tar[id] - now) / v[id][pos];
        assert(owo <= 1);
        rem[pos] = rem[pos] - owo;
        x[it] = pos - rem[pos];
    }
    return true;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // nyanyanyanyanya
    int n, l; cin >> n >> l;
    assert(n <= 6);
    For(i, 1, n) {
        tar[i] = Frac();
        For(j, 1, l) {
            cin >> v[i][j];
            tar[i].x += v[i][j];
        }
        tar[i] = tar[i] / n;
    }
    For(i, 1, n) ids[i] = i;
    do {
        if(check(n, l)) {
            For(i, 1, n - 1) cout << x[i].x << " " << x[i].y << "\n";
            For(i, 1, n) cout << ids[i] << " \n"[i == n];
            return 0;
        }
    } while(next_permutation(ids + 1, ids + n + 1));
    assert(false);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 476 KB Output is correct
12 Correct 1 ms 452 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 476 KB Output is correct
12 Correct 1 ms 452 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 444 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 440 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 436 KB Output is correct
24 Correct 3 ms 452 KB Output is correct
25 Correct 1 ms 444 KB Output is correct
26 Correct 1 ms 444 KB Output is correct
27 Correct 1 ms 432 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 444 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 448 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 2 ms 448 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Runtime error 1 ms 724 KB Execution killed with signal 6
44 Halted 0 ms 0 KB -