Submission #171001

#	Time	Username	Problem	Language	Result	Execution time	Memory
171001		errorgorn	Naan (JOI19_naan)	C++14	100 / 100	1130 ms	210360 KiB

naan

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct fraction{
    long long a,b;
    fraction(){
        a=0;
        b=1;
    }
    fraction (long long i, long long _a, long long _b){
        a=_a;
        b=_b;
        a+=i*b;
    }
    long long whole(){
        return a/b;
    }
    bool bigger(fraction *i){
        if (whole()!=i->whole()){
            return whole()<i->whole();
        }
        else{
            return (a-(b*whole()))*i->b<(i->a-(i->b*whole()))*b;
        }
	}
};
int n,l;
long long arr[2005][2005];
fraction *split[2005][2005];
vector<int> rem;
int perm[2005];
int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&l);
    long long total,curr_total;
    long long inc,val;
    int pointer;
    for (int x=1;x<=n;x++){
        total=0;
        for (int y=0;y<l;y++){
            scanf("%lld",&arr[x][y]);
            arr[x][y]*=n;
            total+=arr[x][y];
        }
        inc=total/n;
        val=inc;
        pointer=0;
        curr_total=0;
        while (val!=total){
            while (val<curr_total+arr[x][pointer]){
                split[x][val/inc]=new fraction(pointer, val-curr_total,arr[x][pointer]);
                val+=inc;
            }
            curr_total+=arr[x][pointer];
            pointer++;
        }
        rem.push_back(x);
    }
    pointer=1;
    int best_index;
    int index;
    while (rem.size()>1){
        best_index=-1;
        for (int x=0;x<rem.size();x++){
            index=rem[x];
            if (best_index==-1 || split[index][pointer]->bigger(split[best_index][pointer])){
                best_index=index;
            }
        }
        printf("%lld %lld\n",split[best_index][pointer]->a,split[best_index][pointer]->b);
        rem.erase(find(rem.begin(),rem.end(),best_index));
        perm[pointer]=best_index;
        pointer++;
    }
    for (int x=1;x<n;x++){
        printf("%d ",perm[x]);
    }
    printf("%d\n",rem[0]);
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int x=0;x<rem.size();x++){
                      ~^~~~~~~~~~~
naan.cpp:35: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:42:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld",&arr[x][y]);
             ~~~~~^~~~~~~~~~~~~~~~~~~

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