Submission #1057712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057712		hotboy2703	Naan (JOI19_naan)	C++17	100 / 100	221 ms	123220 KiB

naan

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e3+100;
const ll INF = 1e18;
ll n,L;
ll v[MAXN][MAXN];
pll cut[MAXN][MAXN];
bool in[MAXN];
ll p[MAXN];
pll sus[MAXN];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>L;
    for (ll i = 1;i <= n; i++){
        ll sum = 0;
        for (ll j = 1;j <= L;j ++){
            cin>>v[i][j];
            v[i][j] *= n;
            sum += v[i][j];
        }
        sum /= n;
        ll A = 0,B = 1;
        for (ll j = 1;j <= n;j ++){
            ll cur = 0;
            while (cur < sum && (B-A%B) * v[i][A/B+1] / B + cur <= sum)cur+=(B-A%B) * v[i][A/B+1] / B,A+=(B-A%B),A/=B,B=1;
            if (cur < sum){
                if (B==1){
                    B=v[i][A/B+1];
                    A *= B;
                }
                A += (sum - cur);
                cur = sum;
            }
            // assert(cur==sum);
            cut[i][j] = MP(A,B);
            // assert(B<=1e9);
            // if (j>1)if(cut[i][j].fi * cut[i][j-1].se <= cut[i][j-1].fi * cut[i][j].se){
            //     cout<<cut[i][j-1].fi<<' '<<cut[i][j-1].se<<' '<<cut[i][j].fi<<' '<<cut[i][j].se<<'\n';
            //     return 0;
            // }
            // cout<<A<<' '<<B<<endl;
        }
    }
    for (ll i = 1; i<= n;i ++)in[i] = 1;
    for (ll j = 1;j <= n;j ++){
        ll best = -1;
        for (ll i = 1;i <= n;i ++){
            if (in[i] == 1){
                if (best==-1)best = i;
                else{
                    ll a1 = cut[best][j].fi,b1 = cut[best][j].se;
                    ll a2 = cut[i][j].fi,b2 = cut[i][j].se;
                    if (__int128_t(a1)*b2>__int128_t(a2)*b1)best = i;
                }
            }
        }
        in[best] = 0;
        p[j]=best;
        sus[j] = cut[best][j];
    }
    for (ll j = 1;j <= n-1;j ++){
        cout<<sus[j].fi<<' '<<sus[j].se<<'\n';
    }
    for (ll j = 1;j <= n;j ++)cout<<p[j]<<' ';
}

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