Submission #254018

#TimeUsernameProblemLanguageResultExecution timeMemory
254018TadijaSebezNaan (JOI19_naan)C++11
29 / 100
733 ms45816 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=2005; struct frac{ ll p,q; frac(){} frac(ll a,ll b=1){if(b<0)a=-a,b=-b;ll g=__gcd(abs(a),b);a/=g;b/=g;p=a;q=b;} frac operator * (ll b) const {return frac(p*b,q);} frac operator - (frac b) const {return frac(p*b.q-b.p*q,q*b.q);} frac operator + (frac b) const {return frac(p*b.q+b.p*q,q*b.q);} frac operator * (frac b) const {return frac(p*b.p,q*b.q);} frac operator / (frac b) const {return frac(p*b.q,q*b.p);} bool operator < (frac b) const {return p*b.q<b.p*q;} void print(){printf("(%lld/%lld)",p,q);} }p[N][N]; frac operator -= (frac&a,frac b){a=a-b;} 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; } int take=0; for(int j=1,ptr=1;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; }

Compilation message (stderr)

naan.cpp: In function 'frac operator-=(frac&, frac)':
naan.cpp:17:40: warning: no return statement in function returning non-void [-Wreturn-type]
 frac operator -= (frac&a,frac b){a=a-b;}
                                        ^
naan.cpp: In function 'int main()':
naan.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~
naan.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i",&v[i][j]);
    ~~~~~^~~~~~~~~~~~~~~
naan.cpp:51:9: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ans[i]=k;
   ~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...