제출 #330549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330549		EndRay	Naan (JOI19_naan)	C++17	24 / 100	95 ms	63364 KiB

naan

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2000+1;

struct fraction{
    ll num, den;
    fraction(ll num=0, ll den=1):num(num), den(den){}

    void normalize(){
        ll g = __gcd(num, den);
        num /= g;
        den /= g;
        if(den < 0){
            num = -num;
            den = -den;
        }
    }

    fraction operator-(){
        return fraction{-num, den};
    }

    fraction operator+=(const fraction& b){
        num = num*b.den + den*b.num;
        den = den*b.den;
        normalize();
        return *this;
    }
    fraction operator-=(const fraction& b){
        num = num*b.den - den*b.num;
        den = den*b.den;
        normalize();
        return *this;
    }
    fraction operator*=(const fraction& b){
        num = num*b.num;
        den = den*b.den;
        normalize();
        return *this;
    }
    fraction operator/=(const fraction& b){
        num = num*b.den;
        den = den*b.num;
        normalize();
        return *this;
    }

    bool operator==(const fraction& b){return num*b.den == den*b.num;}
    bool operator<(const fraction& b){return num*b.den < den*b.num;}
    bool operator>(const fraction& b){return num*b.den > den*b.num;}
    bool operator<=(const fraction& b){return num*b.den <= den*b.num;}
    bool operator>=(const fraction& b){return num*b.den >= den*b.num;}
};

fraction operator+(fraction a, const fraction& b){return (a += b);}
fraction operator-(fraction a, const fraction& b){return (a -= b);}
fraction operator*(fraction a, const fraction& b){return (a *= b);}
fraction operator/(fraction a, const fraction& b){return (a /= b);}

int n, l;
ll v[N][N];
ll sum[N];
fraction split[N][N];
bool used[N];
fraction ans[N];
int p[N];

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> n >> l;
    for(int i = 0; i < n; ++i)
        for(int j = 1; j <= l; ++j){
            cin >> v[i][j];
            sum[i] += v[i][j];
        }
    for(int i = 0; i < n; ++i){
        split[i][0] = 0;
        split[i][n] = n;
        fraction need = fraction(sum[i], n);
        int k = 1;
        fraction cur_sum = 0;
        for(int j = 1; j < n; ++j){
            for(; cur_sum + v[i][k] <= need*j; ++k)
                cur_sum += v[i][k];
            split[i][j] = k + (need*j-cur_sum)/v[i][k];
        }
    }
    for(int j = 1; j < n; ++j){
        fraction mn = l;
        int mn_i = -1;
        for(int i = 0; i < n; ++i)
            if(!used[i] && mn > split[i][j]){
                mn = split[i][j];
                mn_i = i;
            }
        ans[j] = mn;
        p[j] = mn_i;
        used[mn_i] = true;
    }
    for(int i = 0; i < n; ++i)
        if(!used[i])
            p[n] = i;
    for(int j = 1; j < n; ++j)
        cout << ans[j].num << " " << ans[j].den << "\n";
    for(int j = 1; j <= n; ++j)
        cout << p[j]+1 << " ";
    cout << "\n";
}

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