Submission #310015

#	Time	Username	Problem	Language	Result	Execution time	Memory
310015		YJU	Naan (JOI19_naan)	C++14	100 / 100	727 ms	85508 KiB

naan

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')w=0,ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
#define ll long long
#define pi pair<ll,ll>
#define mk make_pair
#define fi first
#define se second
const int N=2005;
pi p[N][N],ans1[N];int n,m,val[N],vis[N],ans2[N];
bool cmp(pi a,pi b){return (long double)a.fi/a.se<(long double)b.fi/b.se;}
int main(){
    n=gi();m=gi();
    for(int i=1;i<=n;++i){
        ll sum=0,now=0;
        for(int j=1;j<=m;++j)sum+=(val[j]=gi());
        for(int j=1,k=1;j<=n;++j){
            while(k<m&&(now+val[k])*n<sum*j)now+=val[k++];
            ll a=1ll*n*val[k]*(k-1)+sum*j-now*n,b=1ll*n*val[k],d=__gcd(a,b);
            p[i][j]=mk(a/d,b/d);
        }
    }
    for(int i=1;i<=n;++i){
        int x=0;p[x][i]=mk(1,0);
        for(int j=1;j<=n;++j)if(!vis[j])x=cmp(p[j][i],p[x][i])?j:x;
        ans1[i]=p[x][i];ans2[i]=x;vis[x]=1;
    }
    for(int i=1;i<n;++i)printf("%lld %lld\n",ans1[i].fi,ans1[i].se);
    for(int i=1;i<=n;++i)printf("%d ",ans2[i]);return puts(""),0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:36:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |     for(int i=1;i<=n;++i)printf("%d ",ans2[i]);return puts(""),0;
      |     ^~~
naan.cpp:36:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   36 |     for(int i=1;i<=n;++i)printf("%d ",ans2[i]);return puts(""),0;
      |                                                ^~~~~~

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