oj.uz

Submission #702423

# Submission time Handle Problem Language Result Execution time Memory
702423 2023-02-24T04:47:52 Z PixelCat Naan (JOI19_naan) C++14
29 / 100
 214 ms 262144 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;
}
ostream& operator<<(ostream& os, const Frac &a) {
    os << a.x << "/" << a.y;
    return os;
}

const int MAXN = 2010;

struct Meow {
    int v[MAXN];
    Frac tar;
    Frac inq[MAXN];
    Frac rem[MAXN];
    int pos_r, pos_l;
    Frac now;
    bool used;
    void init(int n, int l) {
        used = false;
        tar = Frac();
        For(i, 1, l) {
            cin >> v[i];
            tar.x += v[i];
            rem[i] = Frac(1);
        }
        tar = tar / n;
        pos_r = 1; pos_l = 1;
        now = Frac(0);
        push(1, Frac(0));
    }
    void push(int p0, Frac par) {
        while(pos_l < p0) {
            now = now - inq[pos_l] * v[pos_l];
            pos_l++;
        }
        // cout << rem[pos_r] << " " << tar << " " << now << "\n" << flush;
        Frac t = inq[pos_l] + rem[pos_r] + par - 1;
        inq[pos_l] = inq[pos_l] - t;
        now = now - t * v[pos_l];

        while(now + rem[pos_r] * v[pos_r] < tar) {
            now = now + rem[pos_r] * v[pos_r];
            inq[pos_r] = inq[pos_r] + rem[pos_r];
            rem[pos_r] = 0;
            pos_r++;
        }
        t = (tar - now) / v[pos_r];
        assert(t <= rem[pos_r]);
        rem[pos_r] = rem[pos_r] - t;
        inq[pos_r] = inq[pos_r] + t;
        now = tar;
    }
    pair<int, Frac> get_front() {
        return make_pair(pos_r, 1 - rem[pos_r]);
    }
} meow[MAXN];

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) meow[i].init(n, l);
    vector<int> ans;
    For(i, 1, n - 1) {
        pair<int, Frac> front(l + 1, 0);
        int min_id = -1;
        For(j, 1, n) if(!meow[j].used) {
            if(meow[j].get_front() < front) {
                front = meow[j].get_front();
                min_id = j;
            }
            auto p = meow[j].get_front();
            // cout << j << " : " << p.F << " - " << p.S << "\n" << flush;
        }
        assert(min_id > 0);
        ans.eb(min_id);
        meow[min_id].used = true;
        For(j, 1, n) if(!meow[j].used) {
            meow[j].push(front.F, front.S);
        }
        front.S = front.F - 1 + front.S;
        cout << front.S.x << " " << front.S.y << "\n";
    }
    for(auto &i:ans) cout << i << " ";
    For(i, 1, n) if(!meow[i].used) cout << i << "\n";
    return 0;
}

Compilation message

naan.cpp: In function 'int32_t main()':
naan.cpp:126:18: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  126 |             auto p = meow[j].get_front();
      |                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 134904 KB Output is correct
2 Correct 58 ms 135000 KB Output is correct
3 Correct 52 ms 134900 KB Output is correct
4 Correct 55 ms 134908 KB Output is correct
5 Correct 50 ms 134916 KB Output is correct
6 Correct 51 ms 134988 KB Output is correct
7 Correct 51 ms 134936 KB Output is correct
8 Correct 51 ms 134964 KB Output is correct
9 Correct 58 ms 135048 KB Output is correct
10 Correct 55 ms 135012 KB Output is correct
11 Correct 51 ms 135000 KB Output is correct
12 Correct 52 ms 135116 KB Output is correct
13 Correct 52 ms 134928 KB Output is correct
14 Correct 54 ms 134924 KB Output is correct
15 Correct 52 ms 134924 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 134888 KB Output is correct
2 Correct 51 ms 134988 KB Output is correct
3 Correct 52 ms 134988 KB Output is correct
4 Correct 53 ms 135068 KB Output is correct
5 Correct 53 ms 135072 KB Output is correct
6 Correct 56 ms 134988 KB Output is correct
7 Correct 53 ms 134988 KB Output is correct
8 Correct 56 ms 134900 KB Output is correct
9 Correct 53 ms 135044 KB Output is correct
10 Correct 53 ms 135116 KB Output is correct
11 Correct 54 ms 134988 KB Output is correct
12 Correct 59 ms 134880 KB Output is correct
13 Correct 53 ms 134972 KB Output is correct
14 Correct 61 ms 135060 KB Output is correct
15 Correct 54 ms 134984 KB Output is correct
16 Correct 57 ms 135056 KB Output is correct
17 Correct 60 ms 134984 KB Output is correct
18 Correct 53 ms 134988 KB Output is correct
19 Correct 62 ms 135044 KB Output is correct
20 Correct 55 ms 135036 KB Output is correct
21 Correct 54 ms 134980 KB Output is correct
22 Correct 52 ms 134984 KB Output is correct
23 Correct 54 ms 134904 KB Output is correct
24 Correct 55 ms 134988 KB Output is correct
25 Correct 53 ms 134976 KB Output is correct
26 Correct 59 ms 134920 KB Output is correct
27 Correct 54 ms 134980 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 134904 KB Output is correct
2 Correct 58 ms 135000 KB Output is correct
3 Correct 52 ms 134900 KB Output is correct
4 Correct 55 ms 134908 KB Output is correct
5 Correct 50 ms 134916 KB Output is correct
6 Correct 51 ms 134988 KB Output is correct
7 Correct 51 ms 134936 KB Output is correct
8 Correct 51 ms 134964 KB Output is correct
9 Correct 58 ms 135048 KB Output is correct
10 Correct 55 ms 135012 KB Output is correct
11 Correct 51 ms 135000 KB Output is correct
12 Correct 52 ms 135116 KB Output is correct
13 Correct 52 ms 134928 KB Output is correct
14 Correct 54 ms 134924 KB Output is correct
15 Correct 52 ms 134924 KB Output is correct
16 Correct 54 ms 134888 KB Output is correct
17 Correct 51 ms 134988 KB Output is correct
18 Correct 52 ms 134988 KB Output is correct
19 Correct 53 ms 135068 KB Output is correct
20 Correct 53 ms 135072 KB Output is correct
21 Correct 56 ms 134988 KB Output is correct
22 Correct 53 ms 134988 KB Output is correct
23 Correct 56 ms 134900 KB Output is correct
24 Correct 53 ms 135044 KB Output is correct
25 Correct 53 ms 135116 KB Output is correct
26 Correct 54 ms 134988 KB Output is correct
27 Correct 59 ms 134880 KB Output is correct
28 Correct 53 ms 134972 KB Output is correct
29 Correct 61 ms 135060 KB Output is correct
30 Correct 54 ms 134984 KB Output is correct
31 Correct 57 ms 135056 KB Output is correct
32 Correct 60 ms 134984 KB Output is correct
33 Correct 53 ms 134988 KB Output is correct
34 Correct 62 ms 135044 KB Output is correct
35 Correct 55 ms 135036 KB Output is correct
36 Correct 54 ms 134980 KB Output is correct
37 Correct 52 ms 134984 KB Output is correct
38 Correct 54 ms 134904 KB Output is correct
39 Correct 55 ms 134988 KB Output is correct
40 Correct 53 ms 134976 KB Output is correct
41 Correct 59 ms 134920 KB Output is correct
42 Correct 54 ms 134980 KB Output is correct
43 Runtime error 214 ms 262144 KB Execution killed with signal 6
44 Halted 0 ms 0 KB -