제출 #1057629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057629		hotboy2703	Naan (JOI19_naan)	C++17	29 / 100	130 ms	80212 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);
            }
            cut[i][j] = MP(A,B);
            // 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 (a1*b2>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: 0 / 71