Submission #1275348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275348		tvgk	Naan (JOI19_naan)	C++20	29 / 100	127 ms	4780 KiB

naan

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 2e3 + 7, inf = 1e9;

struct frac
{
    ll u, v;

    frac() {};
    frac(int uu, int vv)
    {
        u = uu;
        v = vv;
    }

    frac mini()
    {
        ll tmp = __gcd(u, v);
        u /= tmp;
        v /= tmp;
        return *this;
    }

    friend frac operator-(int a, frac b)
    {
        b.u = b.v * a - b.u;
        return b.mini();
    }

    friend frac operator-(frac a, frac b)
    {
        a.u = a.u * b.v - a.v * b.u;
        a.v *= b.v;
        return a.mini();
    }

    friend frac operator+(frac a, frac b)
    {
        a.u = a.u * b.v + a.v * b.u;
        a.v *= b.v;
        return a.mini();
    }

    friend frac operator*(int a, frac b)
    {
        b.u *= a;
        return b.mini();
    }

    friend frac operator/(frac b, int a)
    {
        b.v *= a;
        return b.mini();
    }

    friend bool operator<(frac a, frac b)
    {
        return a.u * b.v < a.v * b.u;
    }

    frac small()
    {
        int tmp = v;
        while (tmp > 1e9)
            tmp /= 2;
        u = (int64_t(u) * tmp + v - 1) / v;
        v = tmp;
        return *this;
    }
};

int n, m, mm, sum[mxN], cur;
ll a[mxN][mxN];
frac tmp[mxN];
bool ers[mxN];
vector<int> ans;
vector<frac> point;

bool cmp(int s, int t)
{
    return a[t][cur] * tmp[s] < a[s][cur] * tmp[t];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            sum[i] += a[i][j];
        }
    }

    frac in;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            tmp[j] = {sum[j], n};

        vector<int> pos;
        while (pos.empty() && cur <= m)
        {
            for (int j = 1; j <= n; j++)
            {
                if (ers[j])
                    continue;

                if (a[j][cur] * (1 - in) < tmp[j])
                    tmp[j] = tmp[j] - a[j][cur] * (1 - in);
                else
                    pos.push_back(j);
            }

            if (pos.empty())
            {
                cur++;
                in = {0, 1};
            }
        }

        if (pos.empty())
        {
            cout << -1;
            return 0;
        }

        sort(pos.begin(), pos.end(), cmp);
        ers[pos[0]] = 1;
        ans.push_back(pos[0]);
        in = in + tmp[pos[0]] / a[pos[0]][cur];
        in.small();
        point.push_back(frac(cur - 1, 1) + in);
    }

    point.pop_back();
    for (frac i : point)
        cout << i.u << " " << i.v << '\n';
    for (int i : ans)
        cout << i << " ";
}

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