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>
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |