Submission #279630

#	Time	Username	Problem	Language	Result	Execution time	Memory
279630		MKopchev	Naan (JOI19_naan)	C++14	29 / 100	287 ms	22776 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];

pair<long long,long long> compress(long long up,long long down)
{
    long long g=__gcd(up,down);
    up=up/g;
    down=down/g;
    return {up,down};
}

pair<long long,long long> add(pair<long long,long long> a,pair<long long,long long> b)
{
    long long up=a.first*b.second+a.second*b.first,down=a.second*b.second;

    return compress(up,down);
}

pair<long long,long long> sub(pair<long long,long long> a,pair<long long,long long> b)
{
    long long up=a.first*b.second-a.second*b.first,down=a.second*b.second;

    return compress(up,down);
}

bool at_most(pair<long long,long long> a,pair<long long,long long> b)
{
    return __int128(a.first)*b.second<=__int128(a.second)*b.first;
    //return a.first*b.second<=a.second*b.first;
}

pair<long long,long long> 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++)
    {
        pair<long long,long long> where={0,1};

            for(int t=1;t<=n;t++)
            {
                pair<long long,long long> cur_where=where,remain={pref[j],n};

                int id=cur_where.first/cur_where.second+1;

                while(id<=m)
                {
                    pair<long long,long long> cur=sub({id,1},cur_where);
                    cur.first=cur.first*inp[j][id];

                    //cout<<id<<" "<<cur_where.first<<" "<<cur_where.second<<" "<<remain.first<<" "<<remain.second<<" "<<cur.first<<" "<<cur.second<<endl;

                    if(at_most(remain,cur))
                    {
                        cur_where=add(cur_where,{remain.first,remain.second*inp[j][id]});

                        long long g=__gcd(cur_where.first,cur_where.second);
                        cur_where.first=cur_where.first/g;
                        cur_where.second=cur_where.second/g;

                        //cout<<"became "<<cur_where.first<<" "<<cur_where.second<<" "<<remain.first<<" "<<remain.second<<" "<<inp[t][id]<<endl;

                        cut[j][t]=cur_where;
                        break;
                    }
                    else
                    {
                        cur_where={id,1};

                        remain=sub(remain,cur);

                        id++;
                    }
                }

                //cout<<j<<" "<<t<<" -> "<<cut[j][t].first<<" "<<cut[j][t].second<<endl;
                where=cut[j][t];
            }
    }

    pair<long long,long long> where={0,1};

    for(int t=1;t<=n;t++)
    {
        pair<long long,long long> mini={m,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.first,mini.second);

        assert(at_most(mini,{m,1}));

        if(t!=n)printf("%lld %lld\n",mini.first,mini.second);

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

        where=mini;
    }



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

Compilation message (stderr)

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

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