oj.uz

Submission #279595

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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 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 384 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 416 KB Output is correct
9 Correct 0 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 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 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 1 ms 384 KB Output is correct
4 Correct 1 ms 384 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 2 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 1 ms 384 KB Output is correct
15 Correct 1 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 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 384 KB Output is correct
24 Correct 1 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 1 ms 384 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 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 384 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 416 KB Output is correct
9 Correct 0 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 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 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 1 ms 384 KB Output is correct
19 Correct 1 ms 384 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 2 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 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 2 ms 384 KB Output is correct
34 Correct 2 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 384 KB Output is correct
39 Correct 1 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 1 ms 384 KB Output is correct
43 Runtime error 49 ms 6904 KB Execution killed with signal 8
44 Halted 0 ms 0 KB -