/*
*/
#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> pos){
/*if(pos.b==0){
while(true){
continue;
}
}*/
pair<llo,llo> val={aa[ind][pos.a/pos.b]*(pos.b-(pos.a%pos.b)),pos.b};
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);
return {aa.a/cc,aa.b/cc};
}
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);
//cout<<j<<":"<<x.a<<":"<<x.b<<endl;
/*if(pos.a/pos.b>=l){
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;
}
}
*/
tt.b*=aa[j][pos.a/pos.b];
/* 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);
}
ans.pb(ans5);
cur.erase(ans5-1);
if(i<n-1){
ans2.pb(pos);
}
}
ans.pb(*(cur.begin()));
for(auto j:ans2){
cout<<j.a<<" "<<j.b<<endl;
}
for(auto j:ans){
cout<<j<<" ";
}
cout<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Integer parameter [name=P_i] equals to 0, violates the range [1, 2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Integer parameter [name=P_i] equals to 0, violates the range [1, 2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Integer parameter [name=P_i] equals to 0, violates the range [1, 2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
