Submission #162935

#	Time	Username	Problem	Language	Result	Execution time	Memory
162935		combi1k1	Naan (JOI19_naan)	C++14	100 / 100	734 ms	112568 KiB

naan

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define pb  push_back

#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)

const int   N   = 2e3 + 1;
const int   inf = 1e9 + 7;

struct Frac {
    ll  int_part;
    ll  upper;
    ll  lower;

    Frac(ll a = 0,ll b = 0,ll c = 0)    {
        int_part = a;
        upper = b;
        lower = c;
        if (b > c)  {
            int_part += b / c;
            upper %= c;
        }

        if (c < 0)
            upper *= (-1),
            lower *= (-1);
    };
};
bool operator < (const Frac &lhs,const Frac &rhs)   {
    if (lhs.int_part != rhs.int_part)
        return  lhs.int_part < rhs.int_part;

    return  lhs.upper * rhs.lower < lhs.lower * rhs.upper;
}
ostream & operator << (ostream &out,Frac &C)    {
    ll  g = __gcd(C.upper,C.lower);
    C.upper /= g;
    C.lower /= g;

    ll  a = C.int_part * C.lower + C.upper;
    ll  b = C.lower;

    out << a << " ";
    out << b << "\n";
    return  out;
}

int v[N][N];
ll  s[N];

vector<Frac> cut[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int L;  cin >> L;

    FOR(i,0,n)  FOR(j,0,L)  {
        cin >>  v[i][j];
        s[i] += v[i][j];
    }

    FOR(i,0,n)  {
        ll  sum = 0;
        int ptr = 0;

        FOR(j,1,n)  {
            for(; (sum +  v[i][ptr]) * n <= s[i] * j ; ++ptr)
                   sum += v[i][ptr];

            ll  lower = v[i][ptr] * n;
            ll  upper = s[i] * j - sum * n;

            cut[i].pb({ptr,upper,lower});
        }
        cut[i].pb({L,0,1});
    }

    vector<int> perm;
    vector<int> have;

    FOR(i,0,n)  have.push_back(i);
    FOR(i,0,n)  {
        sort(have.begin(),have.end(),[&](int x,int y)   {
            return  cut[y][i] < cut[x][i];
        });
        perm.push_back(have.back());
        have.pop_back();

        if (i < n - 1)  cout << cut[perm.back()][i];
    }
    for(int x : perm)   cout << x + 1 << " ";
}
/*
2 5
2 7 1 8 2
3 1 4 1 5
*/

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