Submission #279645

#	Time	Username	Problem	Language	Result	Execution time	Memory
279645		MKopchev	Naan (JOI19_naan)	C++14	100 / 100	1058 ms	134520 KiB

naan

#include<bits/stdc++.h>
using namespace std;

const int nmax=2e3+42;

int n,m;

int inp[nmax][nmax],pref[nmax];

int outp[nmax];
bool used[nmax];

struct number
{
    long long whole,up,down;
};

number compress(number a)
{
    long long g=__gcd(a.up,a.down);
    a.up=a.up/g;
    a.down=a.down/g;
    return a;
}

number add(number a,number b)
{
    a.whole=a.whole+b.whole;
    a.up=a.up*b.down+a.down*b.up;
    a.down=a.down*b.down;

    a.whole=a.whole+a.up/a.down;
    a.up=a.up/a.down;

    return compress(a);
}

bool at_most(number a,number b)
{
    if(a.whole!=b.whole)return a.whole<b.whole;

    return a.up*b.down<=a.down*b.up;
}

number cut[nmax][nmax];

int pointer[nmax];

int main()
{
    scanf("%i%i",&n,&m);

    for(int i=1;i<=n;i++)
    {
        pointer[i]=1;
        for(int j=1;j<=m;j++)
        {
            scanf("%i",&inp[i][j]);
            pref[i]+=inp[i][j];
        }
    }

    for(int j=1;j<=n;j++)
    {
        int id=1,sum=0;

        for(int t=1;t<=n;t++)
        {
            pair<long long,long long> wanted={1LL*t*pref[j],n};

            while(id<=m&&wanted.second*(sum+inp[j][id])<=wanted.first)
            {
                sum=sum+inp[j][id];
                id++;
            }

            cut[j][t].whole=id-1;
            cut[j][t].up=wanted.first-sum*wanted.second;
            cut[j][t].down=wanted.second*inp[j][min(m,id)];

            //cout<<j<<" "<<t<<" -> "<<cut[j][t].whole<<" "<<cut[j][t].up<<" "<<cut[j][t].down<<endl;

            cut[j][t]=compress(cut[j][t]);

            //cout<<j<<" "<<t<<" -> "<<id<<" "<<cut[j][t].whole<<" "<<cut[j][t].up<<" "<<cut[j][t].down<<endl;
        }
    }

    for(int t=1;t<=n;t++)
    {
        number mini;mini.whole=m;mini.up=0;mini.down=1;

        int which=-1;

        for(int j=1;j<=n;j++)
            if(used[j]==0)
            {
                if(at_most(cut[j][t],mini))
                {
                    mini=cut[j][t];
                    which=j;
                }
            }

        mini=compress(mini);

        if(t!=n)printf("%lld %lld\n",mini.up+mini.whole*mini.down,mini.down);

        outp[t]=which;
        used[which]=1;
    }



    for(int i=1;i<=n;i++)printf("%i ",outp[i]);
    return 0;
}

Compilation message (stderr)

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

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