Submission #703806

#	Time	Username	Problem	Language	Result	Execution time	Memory
703806		Darren0724	Naan (JOI19_naan)	C++17	100 / 100	496 ms	262144 KiB

naan

#include <bits/stdc++.h>
using namespace std;
#define int __int128
#define pii pair<int,int>
const int INF=1e18;
bool operator<(pair<int,int> a,pair<int,int> b){
    return a.first*b.second<a.second*b.first;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;

    long long n1,m1;cin>>n1>>m1;
    n=n1,m=m1;
    vector<int> a(n);
    vector<vector<int>> v(n,vector<int>(m)),pre(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            long long tmp=0;cin>>tmp;
            v[i][j]=tmp;
            v[i][j]*=n;
            a[i]+=v[i][j];
        }
        a[i]/=n;
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<v[i][j]<<' ';
        }
        cout<<endl;
    }*/
    for(int i=0;i<n;i++){
        pre[i][0]=v[i][0];
        for(int j=1;j<m;j++){
            pre[i][j]=pre[i][j-1]+v[i][j];
        }
    }
    vector<bool> vis(n);
    vector<vector<pair<int,int>>> rec(n,vector<pair<int,int>>(n));
    for(int i=0;i<n;i++){
        int need=0;
        int ptr=0;
        for(int j=0;j<n-1;j++){
            need+=a[i];
            while(ptr<m&&pre[i][ptr]<need){
                ptr++;
            }
            int p=(ptr>0?pre[i][ptr-1]:0);
            rec[i][j]={need-p+ptr*v[i][ptr],v[i][ptr]};
        }
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<"("<<rec[i][j].first<<","<<rec[i][j].second<<") ";
        }
        cout<<endl;
    }*/
    vector<int> ans(n);
    for(int i=0;i<n-1;i++){
        int idx=-1;
        for(int j=0;j<n;j++){
            if(vis[j]){
                continue;
            }
            if(idx==-1){
                idx=j;
            }
            else if(rec[j][i]<rec[idx][i]){
                idx=j;
            }
        }
        ans[i]=idx+1;
        vis[idx]=1;
        cout<<(long long)rec[idx][i].first<<' '<<(long long)rec[idx][i].second<<endl;
    }
    for(int i=0;i<n;i++){
        if(vis[i]==0){
            ans[n-1]=i+1;
        }
    }
    for(int j=0;j<n;j++){
        cout<<(long long)ans[j]<<' ';
    }




    return 0;
}

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