Submission #702428

#	Time	Username	Problem	Language	Result	Execution time	Memory
702428		PixelCat	Naan (JOI19_naan)	C++14	29 / 100	119 ms	262144 KiB

naan

#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 {
    __int128_t 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 << (LL)a.x << "/" << (LL)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;
        }
        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 << (LL)front.S.x << " " << (LL)front.S.y << "\n";
    }
    for(auto &i:ans) cout << i << " ";
    For(i, 1, n) if(!meow[i].used) cout << i << "\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71