/*
*/
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
llo n,l;
llo aa[2001][2001];
pair<llo,llo> cost[2001];
llo su[2001];
pair<llo,llo> add(pair<llo,llo> cur,llo ind,pair<llo,llo> pos2){
/*if(pos.b==0){
while(true){
continue;
}
}*/
pair<llo,llo> val={aa[ind][pos2.a/pos2.b]*(pos2.b-(pos2.a%pos2.b)),pos2.b};
val=simp(val);
return {cur.a*val.b+cur.b*val.a,val.b*cur.b};
}
llo gcd(llo aa,llo bb){
if(aa==0){
return bb;
}
return gcd(bb%aa,aa);
}
pair<llo,llo> simp(pair<llo,llo> aa){
llo cc=gcd(aa.a,aa.b);
aa.a/=cc;
aa.b/=cc;
if(aa.b>1e9){
llo xx=aa.b/1e9;
aa.a/=xx;
aa.a+=1;
aa.b=1e9;
}
return aa;
}
pair<llo,llo> simp2(pair<llo,llo> aa){
llo cc=gcd(aa.a,aa.b);
aa.a/=cc;
aa.b/=cc;
/*if(aa.b>1e9){
return simp2()
return simp2({(aa.a+1)/2,(aa.b+1)/2});
}*/
return aa;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>l;
for(llo i=0;i<n;i++){
for(llo j=0;j<l;j++){
cin>>aa[i][j];
su[i]+=aa[i][j];
}
}
set<llo> cur;
for(llo i=0;i<n;i++){
cur.insert(i);
}
vector<llo> ans;
vector<pair<llo,llo>> ans2;
pair<llo,llo> pos={0,1};
for(llo i=0;i<n-1;i++){
for(llo j=0;j<n;j++){
cost[j]={0,1};
}
llo ans5=-1;
while(true){
llo st=0;
pair<llo,llo> mi={-1,-1};
//cout<<pos.a<<","<<pos.b<<endl;
for(auto j:cur){
pair<llo,llo> x=add(cost[j],j,pos);
x=simp(x);
//cout<<j<<":"<<x.a<<":"<<x.b<<endl;
/*if(pos.a/pos.b>=l){
while(true){
continue;
}
}*/
/*if(aa[j][pos.a/pos.b]==0){
while(true){
continue;
}
}*/
if(x.a*n>=x.b*su[j]){
pair<llo,llo> tt={su[j]*cost[j].b-cost[j].a*n,n*cost[j].b};
tt=simp(tt);
/* if(pos.b==0){
while(true){
continue;
}
}
*/
/* if(pos.a/pos.b>=l){
while(true){
continue;
}
}*/
/*if(aa[j][pos.a/pos.b]==0){
while(true){
continue;
}
}*/
tt.b*=aa[j][pos.a/pos.b];
tt=simp(tt);
/*if(pos.a>=pos.b*l){
while(true){
continue;
}
}*/
/* if(aa[j][pos.a/pos.b]==0){
while(true){
continue;
}
}
*/
// cout<<tt.a<<":"<<tt.b<<endl;
/*if(tt.b==0){
while(true){
continue;
}
}*/
tt={tt.a*pos.b+tt.b*pos.a,pos.b*tt.b};
tt=simp(tt);
if(mi.a==-1){
mi=tt;
st=j+1;
}
else{
if(tt.a*mi.b<tt.b*mi.a){
st=j+1;
mi=tt;
}
}
continue;
}
cost[j]=x;
}
if(st>0){
/* if(mi.b==0){
while(true){
continue;
}
}*/
pos=simp(mi);
ans5=st;
break;
}
pos.a+=pos.b-(pos.a%pos.b);
/*if(pos.a>=pos.b*l){
while(true){
continue;
}
}*/
}
/* while(pos.b>(llo)(2000000000000)){
pos={(pos.a/(llo)2)+1,pos.b/(llo)2};
}*/
/*if(pos.b>2000000000000){
pos.b=2000000000000;
}*/
ans.pb(ans5);
cur.erase(ans5-1);
if(i<n-1){
ans2.pb(pos);
}
}
ans.pb((*(cur.begin()))+1);
for(auto j:ans2){
cout<<j.a<<" "<<j.b<<endl;
}
for(auto j:ans){
cout<<j<<" ";
}
cout<<endl;
return 0;
}
Compilation message
naan.cpp: In function 'std::pair<long int, long int> add(std::pair<long int, long int>, llo, std::pair<long int, long int>)':
naan.cpp:23:6: error: 'simp' was not declared in this scope
val=simp(val);
^~~~
naan.cpp:23:6: note: suggested alternative: 'stime'
val=simp(val);
^~~~
stime
