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 10000000000000
#define N 2019
#define MOD 998244353
using namespace std;
#define greater bos
struct frac {
ll 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 1.0*a.u/a.d>=1.0*b.u/b.d;
}
bool greater(frac a,frac b) {
return 1.0*a.u/a.d>1.0*b.u/b.d;
}
frac gmin(frac a,frac b) {
return greater(a,b)?b:a;
}
int gnext(frac a) {
return a.u/a.d+1;
}
frac app(frac a) {
ll g=__gcd(abs(a.u),abs(a.d));
return {a.u/g,a.d/g};
}
int n,l;
int v[N][N],pre[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]);
pre[i][j]=pre[i][j-1]+v[i][j];
req[i].u+=v[i][j];
}
}
for(int i=1;i<=n;i++) {
cp[i].pb({0,1});
for(int j=1;j<=n;j++) {
int bas=1,son=l;
while(bas<=son) {
if((ll)pre[i][orta]*n<(ll)req[i].u*j) bas=orta+1;
else son=orta-1;
}
// w==(j*sum-n*pre[i][son]+son*v[i][bas]*n)/v[i][bas]*n
cp[i].pb(app({(ll)j*pre[i][l]-(ll)n*pre[i][son]+(ll)son*v[i][bas]*n,(ll)v[i][bas]*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) {
if(greater(mn,cp[j][ptr[j]+1])) {
mn=cp[j][ptr[j]+1];
tut=j;
}
}
}
ans.pb(tut);
u[tut]=1;
res.pb(mn);
}
res.ppb();
for(auto x:res) printf("%lld %lld\n",x.u,x.d);
for(auto x:ans) printf("%d ",x);
}
Compilation message (stderr)
naan.cpp: In function 'int main()':
naan.cpp:110: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:118: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... |