Submission #163068

#	Time	Username	Problem	Language	Result	Execution time	Memory
163068		georgerapeanu	Naan (JOI19_naan)	C++11	29 / 100	891 ms	3704 KiB

naan

#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 2000;
const int LMAX = 2000;

int n,l;
int v[NMAX + 5][LMAX + 5];
bool taken[NMAX + 5];
int perm[NMAX + 5];

long long gcd(long long a,long long b){
    if(b == 0){
        return a;
    }
    return gcd(b,a % b);
}

struct frac_t{
    long long p,q;
    long long num;

    frac_t(long long val = 0){
        this->p = 0;
        this->q = 1;
        this->num = val;
    }

    frac_t operator + (const frac_t &other)const{
        frac_t ans;
        ans.num = this->num + other.num;
        ans.q = this->q * other.q;
        ans.p = this->p * other.q + other.p * this->q;
        long long g = gcd(ans.p,ans.q);
        ans.p /= g;
        ans.q /= g;
        ans.num += ans.p / ans.q;
        ans.p %= ans.q;
        return ans;
    }
    
    frac_t operator - (const frac_t &other)const{
        frac_t ans;
        ans.num = this->num - other.num;
        ans.q = this->q * other.q;
        ans.p = this->p * other.q - other.p * this->q;

        if(ans.p < 0){
            ans.num += (ans.p / ans.q - 1);
            ans.p -= ans.q * (ans.p / ans.q - 1);
        }
        
        ans.num += ans.p / ans.q;
        ans.p %= ans.q;
        
        long long g = gcd(ans.p,ans.q);
        ans.p /= g;
        ans.q /= g;

        return ans;
    }

    frac_t operator * (const frac_t &other)const{
        frac_t a = *this;
        frac_t b = other;
        
        a.p += a.q * a.num;
        b.p += b.q * b.num;

        long long g1 = gcd(a.p,b.q);
        a.p /= g1;
        b.q /= g1;
        long long g2 = gcd(a.q,b.p);
        a.q /= g2;
        b.p /= g2;

        frac_t ans;

        ans.p = a.p * b.p;
        ans.q = a.q * b.q;

        ans.num = ans.p / ans.q;
        ans.p %= ans.q;

        return ans;
    }

    frac_t operator / (const frac_t &other)const{
        frac_t a = *this;
        frac_t b = other;
        
        a.p += a.q * a.num;
        b.p += b.q * b.num;

        swap(b.p,b.q);

        long long g1 = gcd(a.p,b.q);
        a.p /= g1;
        b.q /= g1;
        long long g2 = gcd(a.q,b.p);
        a.q /= g2;
        b.p /= g2;

        frac_t ans;

        ans.p = a.p * b.p;
        ans.q = a.q * b.q;

        ans.num = ans.p / ans.q;
        ans.p %= ans.q;

        return ans;

    }

    bool operator <= (const frac_t &other)const{///HOPE no overflow
        if(this-> num != other.num){
            return this->num < other.num;
        }
        return this->p * other.q <= other.p * this->q;
    }
};
frac_t lst_cost[NMAX + 5];
frac_t target_cost[NMAX + 5];
frac_t split[NMAX + 5];

int main(){

    scanf("%d %d",&n,&l);

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= l;j++){
            scanf("%d",&v[i][j]);
            target_cost[i] = target_cost[i] + frac_t(v[i][j]);
        }
        target_cost[i] = target_cost[i] / frac_t(n);
    }

    frac_t last_pos(0);

    int cnt_splits = 0;

    frac_t min_increment(0);
    min_increment.p = 1;
    min_increment.q = 2e5;

    while(cnt_splits < n - 1){
        frac_t min_nxt = last_pos + min_increment;
        bool expand = false;
        for(int i = 1;i <= n;i++){
            if(taken[i]){
                continue;
            }
            lst_cost[i] = lst_cost[i] + (frac_t(last_pos.num + 1) - last_pos) * frac_t(v[i][last_pos.num + 1]);
            expand |= (target_cost[i] <= lst_cost[i]);
        }

        last_pos.num++;
        last_pos.p = 0;
        last_pos.q = 1;
        if(expand == false){
            continue;
        }

        frac_t bst_frac;
        int id = -1;

        for(int i = 1;i <= n;i++){
            if(taken[i]){
                continue;
            }
            if(target_cost[i] <= lst_cost[i]){
                frac_t tmp = (lst_cost[i] - target_cost[i]) / frac_t(v[i][last_pos.num]);
                if(id == -1 || bst_frac <= tmp){
                    bst_frac = tmp;
                    id = i;
                }
            }
        }
        
        last_pos = last_pos - bst_frac;

        if(last_pos <= min_nxt){
            min_nxt = last_pos;
        }

        for(int i = 1;i <= n;i++){
            if(taken[i]){
                continue;
            }
            lst_cost[i] = frac_t(0);
        }

        split[++cnt_splits] = last_pos;
        taken[id] = true;
        perm[cnt_splits] = id;


    }

    for(int i = 1;i <= n;i++){
        if(taken[i] == false){
            perm[n] = i;
        }
    }

    for(int i = 1;i < n;i++){
        split[i].p += split[i].num * split[i].q;
        split[i].num = 0;
        printf("%lld %lld\n",split[i].p,split[i].q);
    }

    for(int i = 1;i <= n;i++){
        printf("%d ",perm[i]);
    }

    return 0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&l);
     ~~~~~^~~~~~~~~~~~~~~
naan.cpp:135:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&v[i][j]);
             ~~~~~^~~~~~~~~~~~~~~

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