Submission #524439

#	Time	Username	Problem	Language	Result	Execution time	Memory
524439		ParsaAlizadeh	Naan (JOI19_naan)	C++17	29 / 100	675 ms	77024 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 x, y;
    Ratio() : x(0), y(1) {}
    Ratio(ll x) : x(x), y(1) {}
    Ratio(ll x, ll y) : x(x), y(y) {
        norm();
    }
    void norm() {
        ll g = __gcd(x, y);
        x /= g;
        y /= g;
        if (y < 0) {
            x *= -1;
            y *= -1;
        }
    }
    Ratio operator+(Ratio const& r) const {
        return Ratio{x * r.y + r.x * y, y * r.y};
    }
    Ratio operator*(Ratio const& r) const {
        return Ratio{x * r.x, y * r.y};
    }
    bool operator<(Ratio const& r) const {
        return x * r.y < y * r.x;
    }
};

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{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;
            P[i] = e.snd;
            ans.push_back(e.fst);
            mark[e.snd] = true;
            break;
        }
    }
    for (int i = 0; i < n-1; i++) {
        cout << ans[i].x << ' ' << ans[i].y << '\n';
    }
    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: 0 / 71