oj.uz

Submission #279630

# Submission time Handle Problem Language Result Execution time Memory
279630 2020-08-22T08:33:22 Z MKopchev Naan (JOI19_naan) C++14
29 / 100
 287 ms 22776 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 416 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 0 ms 308 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 416 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 2 ms 512 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 2 ms 384 KB Output is correct
38 Correct 0 ms 308 KB Output is correct
39 Correct 2 ms 384 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 1 ms 384 KB Output is correct
42 Correct 2 ms 384 KB Output is correct
43 Correct 175 ms 10872 KB Output is correct
44 Runtime error 287 ms 22776 KB Execution killed with signal 8
45 Halted 0 ms 0 KB -