Submission #958939

#	Time	Username	Problem	Language	Result	Execution time	Memory
958939		Tuanlinh123	Naan (JOI19_naan)	C++17	29 / 100	563 ms	96664 KiB

naan

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
 
struct frac
{
    ll x=0, y=1;
    frac(){}
    frac(ll x): x(x), y(1) {}
    frac(ll x, ll y): x(x), y(y){}
 
    frac operator + (const frac &o) const
    {
        frac ans={x*o.y+y*o.x, y*o.y};
        ll g=__gcd(ans.x, ans.y);
        ans.x/=g, ans.y/=g;
        return ans;
    }
 
    frac operator - (const frac &o) const
    {
        frac ans={x*o.y-y*o.x, y*o.y};
        ll g=__gcd(ans.x, ans.y);
        ans.x/=g, ans.y/=g;
        return ans;
    }
 
    frac operator / (const ll &v) const
    {
        ll g=__gcd(x, v); 
        frac ans={x/g, v/g*y};
        return ans;
    }
 
    frac operator * (const frac& o) const
    {
        frac ans={x*o.x, y*o.y};
        ll g=__gcd(ans.x, ans.y);
        ans.x/=g, ans.y/=g;
        return ans;
    }
 
    bool operator >= (const frac &o) const
    {
        return x*o.y>=y*o.x;
    }
 
    bool operator <= (const frac &o) const
    {
        return x*o.y<=y*o.x;
    }
};

const ll maxn=2005;
ll v[maxn][maxn];
frac f[maxn][maxn];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m; cin >> n >> m;
    for (ll i=1; i<=n; i++)
    {
        for (ll j=1; j<=m; j++)
            cin >> v[i][j], v[i][j]+=v[i][j-1];
        for (ll j=1; j<=n; j++)
        {
            frac t(v[i][m]*j, n);
            ll lo=1, hi=m;
            while (hi>lo)
            {
                ll mid=(lo+hi)/2;
                if (frac(v[i][mid])>=t)
                    hi=mid;
                else lo=mid+1;
            }
            t=t-frac(v[i][lo-1]);
            f[i][j]=frac(lo-1)+t/(v[i][lo]-v[i][lo-1]);
        }
    }
    vector <bool> used(n+1, 0);
    frac crr;
    vector <pll> res;
    vector <ll> ans;
    for (ll z=1; z<=n; z++)
    {
        pair<frac, ll> Max; Max.se=0;
        for (ll i=1; i<=n; i++)
        {
            if (used[i]) continue;
            if (f[i][z]<=frac(m))
                if (!Max.se || !(f[i][z]>=Max.fi)) 
                    Max={f[i][z], i};
        }
        if (!Max.se) {cout << "-1"; exit(0);}
        crr=Max.fi, used[Max.se]=1;
        res.pb({crr.x, crr.y});
        ans.pb(Max.se);
    }
    res.resize(n-1);
    for (pll i:res) cout << i.fi << " " << i.se << "\n";
    for (ll i:ans) cout << i << " ";
}

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