Submission #131830

#TimeUsernameProblemLanguageResultExecution timeMemory
131830hamzqq9Naan (JOI19_naan)C++14
29 / 100
501 ms8236 KiB
#include<bits/stdc++.h> #define st first #define nd second #define pb push_back #define ppb pop_back #define ii pair<int,int> #define ll long long #define orta ((bas+son)>>1) #define sz(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define inf 1000000000 #define N 2019 #define MOD 998244353 using namespace std; #define greater bos struct frac { int u,d; }; frac mul(frac a,frac b) { ll u=(ll)a.u*b.u; ll d=(ll)a.d*b.d; ll g=__gcd(abs(u),abs(d)); return {u/g,d/g}; } frac dvd(frac a,frac b) { swap(b.u,b.d); return mul(a,b); } frac sub(frac a,frac b) { ll u=(ll)a.u*b.d-(ll)b.u*a.d; ll d=(ll)a.d*b.d; ll g=__gcd(abs(u),abs(d)); return {u/g,d/g}; } frac add(frac a,frac b) { ll u=(ll)a.u*b.d+(ll)b.u*a.d; ll d=(ll)a.d*b.d; ll g=__gcd(abs(u),abs(d)); return {u/g,d/g}; } bool eq(frac a,frac b) { return (ll)a.u*b.d==(ll)b.u*a.d; } bool greateq(frac a,frac b) { return (ll)a.u*b.d>=(ll)b.u*a.d; } bool greater(frac a,frac b) { return (ll)a.u*b.d>(ll)b.u*a.d; } frac gmin(frac a,frac b) { return greater(a,b)?b:a; } int gnext(frac a) { return a.u/a.d+1; } int n,l; int v[N][N],u[N],ptr[N]; frac req[N]; vector<frac> cp[N]; int main() { scanf("%d %d",&n,&l); for(int i=1;i<=n;i++) { req[i]={0,n}; for(int j=1;j<=l;j++) { scanf("%d",&v[i][j]); req[i].u+=v[i][j]; } } for(int i=1;i<=n;i++) { //cerr<<i<<"\n"; frac cur={0,1}; while(sz(cp[i])<n) { //cerr<<cur.u<<" "<<cur.d<<"\n"; cp[i].pb(cur); frac rq=req[i]; for(int j=gnext(cur);j<=l;j++) { //cerr<<j<<" "<<cur.u<<" "<<cur.d<<"\n"; frac df=sub({j,1},cur); frac sum=mul(df,{v[i][j],1}); if(greateq(sum,rq)) { frac go=dvd(rq,{v[i][j],1}); cur=add(cur,go); break ; } else { rq=sub(rq,sum); cur={j,1}; } } } cp[i].pb({l,1}); } for(int i=1;i<=n;i++) { //cerr<<"--------------------------\n"; //for(auto x:cp[i]) printf("%d %d\n",x.u,x.d); } //cerr<<"--------------------------\n"; //cerr<<"OK\n"; vector<frac> res; vector<int> ans; for(int i=1;i<=n;i++) { frac mn={inf,1}; int tut=-1; for(int j=1;j<=n;j++) { if(u[j]) continue ; while(sz(res) && ptr[j]<n && greater(res.back(),cp[j][ptr[j]])) { ++ptr[j]; } if(ptr[j]<n) { mn=gmin(mn,cp[j][ptr[j]+1]); if(eq(mn,cp[j][ptr[j]+1])) { tut=j; } } } ans.pb(tut); u[tut]=1; res.pb(mn); } res.ppb(); for(auto x:res) printf("%d %d\n",x.u,x.d); for(auto x:ans) printf("%d ",x); }

Compilation message (stderr)

naan.cpp: In function 'frac mul(frac, frac)':
naan.cpp:31:11: warning: narrowing conversion of '(u / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
          ~^~
naan.cpp:31:15: warning: narrowing conversion of '(d / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
              ~^~
naan.cpp: In function 'frac sub(frac, frac)':
naan.cpp:50:11: warning: narrowing conversion of '(u / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
          ~^~
naan.cpp:50:15: warning: narrowing conversion of '(d / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
              ~^~
naan.cpp: In function 'frac add(frac, frac)':
naan.cpp:61:11: warning: narrowing conversion of '(u / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
          ~^~
naan.cpp:61:15: warning: narrowing conversion of '(d / g)' from 'long long int' to 'int' inside { } [-Wnarrowing]
  return {u/g,d/g};
              ~^~
naan.cpp: In function 'int main()':
naan.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~
naan.cpp:110:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&v[i][j]);
    ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...