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>
using namespace std;
#define ll __int128_t
int n,l;
vector<vector<int>>v;
ll gc(ll a,ll b){
if(!b)return a;
return gc(b,a%b);
}
class frac{
public:
ll a,b;
frac(ll _a,ll _b):a(_a),b(_b){reduce();}
frac(ll x):a(x),b(1){}
void reduce(){if(ll g=gc(a,b)){a/=g;b/=g;}}
bool operator <(const frac& other){return a*other.b<other.a*b;}
frac operator +( const frac& other){return frac(a*other.b+b*other.a,b*other.b);}
};
pair<vector<pair<ll,ll>>,vector<int>> solve(int N,int L,vector<vector<int>>V){
n=N;l=L;v=move(V);
vector<int>was(n);
vector<int>p(n);
vector<pair<ll,ll>>t(n-1);
vector<ll>s(n);for(int i=0;n>i;++i)for(int j:v[i])s[i]+=j;
vector<vector<frac>>g(n,vector<frac>(n-1,l));
for(int i=0;n>i;++i){
int ind=0;ll kam=0;
for(int j=0;n>j+1;++j){
if(v[i][ind]*n>=kam+s[i]){
g[i][j]=frac((ll)v[i][ind]*n*ind+kam+s[i],v[i][ind]*n);
kam+=s[i];}
else{
int nishar=s[i]+kam-v[i][ind]*n;
while(nishar>v[i][++ind]*n){nishar-=v[i][ind]*n;}
kam=nishar;
g[i][j]=frac((ll)v[i][ind]*n*ind+kam,v[i][ind]*n);}
}
}
for(int i=0;n>i+1;++i){frac cur(l);int ind=0;for(int j=0;n>j;++j)if(!was[j]&&g[j][i]<cur){cur=g[j][i];ind=j;}t[i]={cur.a,cur.b};was[ind]=1;p[i]=ind+1;}
for(int i=0;n>i;++i)if(!was[i])p[n-1]=i+1;
return {t,p};
}
int main()
{
std::ios::sync_with_stdio(0);cin.tie(0);
int N,L;cin>>N>>L;
vector<vector<int>>V(N,vector<int>(L));
for(auto&i:V)for(auto&j:i)cin>>j;
auto [t,p]=solve(N,L,move(V));
if(t.size()==0&&p.size()==0)
cout<<-1<<endl;
else{
for(auto [a,b]:t)
cout<<(long long)a<<" "<<(long long)b<<"\n";
for(int i:p)
cout<<i<<" ";
cout<<"\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |