Submission #279595

#	Time	Username	Problem	Language	Result	Execution time	Memory
279595		MKopchev	Naan (JOI19_naan)	C++14	29 / 100	49 ms	6904 KiB

naan

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

const int nmax=2e3+42;

const long double one=1;

int n,m;

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

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

pair<long long,long long> add(pair<long long,long long> a,pair<long long,long long> b)
{
    return {a.first*b.second+a.second*b.first,a.second*b.second};
}

pair<long long,long long> sub(pair<long long,long long> a,pair<long long,long long> b)
{
    return {a.first*b.second-a.second*b.first,a.second*b.second};
}

bool at_most(pair<long long,long long> a,pair<long long,long long> b)
{
    //return a.first*b.second<=a.second*b.first;
    return one*a.first/a.second<=one*b.first/b.second;
}
int main()
{
    scanf("%i%i",&n,&m);

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

    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)
            {
                pair<long long,long long> cur_where=where,remain={pref[j],n};

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

                while(id<=m&&at_most(cur_where,mini))
                {


                    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]});

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

                        if(at_most(cur_where,mini))
                        {
                            mini=cur_where;
                            which=j;
                        }
                        break;
                    }
                    else
                    {
                        cur_where={id,1};

                        remain=sub(remain,cur);

                        id++;
                    }
                }

                //cout<<j<<" -> "<<cur_where.first<<" "<<cur_where.second<<endl;
            }

        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;

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

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

Compilation message (stderr)

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

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