# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
254053 | TadijaSebez | Naan (JOI19_naan) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2005;
struct frac{
ll p,q;
frac():p(0),q(1){}
frac(ll a,ll b=1):p(a),q(b){}
frac operator+(frac b){return frac(p*b.q+b.p*q,q*b.q);}
bool operator<(frac b){return (ldb)p/q<(ldb)b.p/b.q;}
}p[N][N];
int v[N][N],sum[N],ans[N];
bool was[N];
int main(){
int n,l;
scanf("%i %i",&n,&l);
for(int i=1;i<=n;i++){
for(int j=1;j<=l;j++){
scanf("%i",&v[i][j]);
sum[i]+=v[i][j];
v[i][j]*=n;
}
for(int j=1,ptr=1,take=0;j<=n;j++){
int need=sum[i];
while(v[i][ptr]-take<need){
need-=v[i][ptr]-take;
take=0;
ptr++;
}
p[i][j]=frac(ptr-1)+frac(take+need,v[i][ptr]);
take+=need;
}
}
for(int i=1;i<=n;i++){
frac mn=frac(l+1);
int k;
for(int j=1;j<=n;j++)if(!was[j]){
if(p[j][i]<mn){
mn=p[j][i];
k=j;
}
}
if(i!=n)printf("%lld %lld\n",mn.p,mn.q);
ans[i]=k;
was[k]=1;
}
for(int i=1;i<=n;i++)printf("%i ",ans[i]);
return 0;
}