Submission #522688

#	Time	Username	Problem	Language	Result	Execution time	Memory
522688		phamhoanghiep	Naan (JOI19_naan)	C++14	100 / 100	681 ms	150160 KiB

naan

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2002;
struct frac{
    ll who;
    ll num;
    ll den;
    frac (ll _w, ll _n, ll _d): who(_w), num(_n), den(_d) {
        int x=__gcd(num,den);
        num/=x; den/=x;
    };
};
bool cmp(frac a, frac b) {
    if(a.who<b.who) return 1;
    if(a.who>b.who) return 0;
    return a.num*b.den<b.num*a.den;
}
vector<frac> split[maxn];
vector<frac> ans;
ll v[maxn][maxn];
ll sum[maxn];
int n,l;
int p[maxn];
bool used[maxn];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>l;
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<l ; j++) {
            cin>>v[i][j];
            sum[i]+=v[i][j];
        }
    }
    for(int i=0 ; i<n ; i++) {
        ll cur=0;
        ll pos=0;
        for(int j=1 ; j<n ; j++) {
            while((cur+v[i][pos])*n<=sum[i]*j) cur+=v[i][pos++];
            ll rem=sum[i]*j-cur*n;
            split[i].push_back(frac(pos,rem,n*v[i][pos]));
        }
        split[i].push_back(frac(l,0,1));
    }
    for(int i=0 ; i<n ; i++) {
        int nxt=-1;
        for(int j=0 ; j<n ; j++) {
            if(used[j]) continue;
            if(nxt==-1||cmp(split[j][i],split[nxt][i])) nxt=j;
        }
        used[nxt]=1;
        ans.push_back(split[nxt][i]);
        p[i]=nxt;
    }
    ans.pop_back();
    // the one with larger end will always fit in the next window
    // so we can greedy choose the one with smallest split at i
    for(frac tmp: ans) cout<<tmp.who*tmp.den+tmp.num<<' '<<tmp.den<<'\n';
    for(int i=0 ; i<n ; i++) cout<<p[i]+1<<' ';
}

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