제출 #524467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524467		ParsaAlizadeh	Naan (JOI19_naan)	C++17	100 / 100	1484 ms	169212 KiB

naan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define all(x) begin(x), end(x)
#define kill(x) return cout << x << '\n', 0
#define fst first
#define snd second

void assume(int expr) {
    if (!expr) __builtin_unreachable();
}

constexpr int N = 2010;

struct Ratio {
    ll c = 0, x = 0, y = 1;
    Ratio(ll c) : c(c), x(0), y(1) {}
    Ratio(ll c, ll x, ll y) : c(c), x(x), y(y) {
        c += (x / y);
        x -= y * (x / y);
        norm();
    }
    void norm() {
        ll g = __gcd(x, y);
        x /= g;
        y /= g;
    }
    Ratio operator+(Ratio const& r) const {
        return Ratio{c + r.c, x * r.y + r.x * y, y * r.y};
    }
    bool operator<(Ratio const& r) const {
        if (c != r.c)
            return c < r.c;
        return x * r.y < y * r.x;
    }
    void show() const {
        ll p = c * y + x, q = y;
        cout << p << ' ' << q << '\n';
    }
};

int n, L, P[N];
ll V[N][N];
vector<pair<Ratio, int>> E[N];
vector<Ratio> ans;
bitset<N> mark;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> L;
    for (int i = 0; i < n; i++) {
        ll S = 0;
        vector<ll> vec;
        vec.reserve(L+1);
        vec.push_back(0);
        for (int j = 0; j < L; j++) {
            cin >> V[i][j];
            S += V[i][j];
            vec.push_back(S * n);
        }
        for (int j = 1; j <= n; j++) {
            ll x = S * j;
            int k = upper_bound(all(vec), x) - begin(vec);
            k--;
            Ratio start = k;
            x -= vec[k];
            if (k < L)
                start = start + Ratio{0, x, n * V[i][k]};
            E[j].emplace_back(start, i);
        }
    }
    fill(all(P), -1);
    for (int i = 1; i <= n; i++) {
        sort(all(E[i]));
        for (auto const& e : E[i]) {
            if (mark[e.snd])
                continue;
            if (!ans.empty() && e.fst < ans.back())
                continue;
            P[i] = e.snd;
            ans.push_back(e.fst);
            mark[e.snd] = true;
            break;
        }
    }
    for (int i = 0; i < n-1; i++) {
        ans[i].show();
    }
    for (int i = 1; i <= n; i++) {
        cout << P[i]+1 << ' ';
    }
    cout << '\n';
    return 0;
}

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