Submission #124444

#	Time	Username	Problem	Language	Result	Execution time	Memory
124444		songc	Naan (JOI19_naan)	C++14	29 / 100	138 ms	130676 KiB

naan

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, K=1, L;
bool chk[2020];

struct Rat{
    LL p=1, q=0;

    Rat(){}
    Rat(LL x, LL y){p = y, q = x;}

    Rat operator+(const Rat &r)const{
        LL g = __gcd(q*r.p + r.q*p, p*r.p);
        return Rat((q*r.p + r.q*p)/g, p*r.p / g);
    }
    Rat operator-(const Rat &r)const{
        LL g = __gcd(q*r.p - r.q*p, p*r.p);
        return Rat((q*r.p - r.q*p)/g, (p*r.p)/g);
    }
    Rat operator*(const Rat &r)const{
        LL g = __gcd(q*r.q, p*r.p);
        return Rat(q*r.q/g, p*r.p/g);
    }
    Rat operator/(const Rat &r)const{
        LL g = __gcd(q*r.p, p*r.q);
        return Rat(q*r.p/g, p*r.q/g);
    }
    bool operator<(const Rat &r)const{
        return q*r.p < r.q*p;
    }
} A[10][2020], C[2020][2020];

int main(){
    scanf("%d %d", &N, &L);
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=L; j++) {
            scanf("%lld", &A[i][j].q);
            A[i][0] = A[i][0] + A[i][j];
        }
        A[i][0].p = N;
    }
    for (int i=1; i<=N; i++){
        Rat R = Rat(0, 1);
        for (int j=1; j<=N; j++){
            Rat S = A[i][0];
            while (1){
                Rat x = A[i][R.q/R.p+1] * (Rat(R.q/R.p+1, 1) - R);
                if (x < S){
                    S = S - x;
                    R = Rat(R.q/R.p+1, 1);
                }
                else{
                    R = R + (S / A[i][R.q/R.p+1]);
                    break;
                }
            }
            C[i][j] = R;
        }
    }
    vector<int> V;
    for (int i=1; i<=N; i++){
        Rat Min=Rat(L+1, 1);
        int id;
        for (int j=1; j<=N; j++){
            if (chk[j]) continue;
            if (C[j][i] < Min){
                Min = C[j][i];
                id = j;
            }
        }
        if (i<N) printf("%lld %lld\n", Min.q, Min.p);
        V.push_back(id);
        chk[id] = true;
    }
    for (int x : V) printf("%d ", x);
    return 0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:37: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:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &A[i][j].q);
             ~~~~~^~~~~~~~~~~~~~~~~~~~

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