This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define f first
#define s second
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
const int maxn=2009;
int n,l,p[maxn],v[maxn][maxn];
bitset<maxn>us;
main(){
IOS;
cin>>n>>l;
REP(i,0,n){
v[i][0]=0;
REP(j,0,l)cin>>v[i][j+1],v[i][j+1]+=v[i][j];
}
pii cur={0,1};
REP(i,1,n){
int opt=-1;
pii ls={1,0};
REP(j,0,n){
if(us[j])continue;
int k=cur.f/cur.s;
pii t={v[j][k]*n*cur.s+(v[j][k+1]-v[j][k])*(cur.f%cur.s)*n+v[j][l]*cur.s,n*cur.s};
// assert(v[j][k]*n*cur.s<7e18);
while((__int128)v[j][k+1]*t.s<=t.f)++k;
int vv=v[j][k+1]-v[j][k];
assert((((__int128)t.f)*n+t.s-1)/t.s<4e11);
if(t.s<0)return 0;
assert(((__int128)t.f)*n>=0);
t={k*vv*n+(((__int128)t.f)*n+t.s-1)/t.s-v[j][k]*n,vv*n};
if((__int128)t.f*ls.s<(__int128)ls.f*t.s)opt=j,ls=t;
}
p[i]=opt;
us[opt]=1;
cur=ls;
cout<<ls.f<<" "<<ls.s<<endl;
}
REP(i,1,n)cout<<p[i]+1<<" ";
REP(i,0,n)if(!us[i])cout<<i+1<<endl;
}
Compilation message (stderr)
naan.cpp:16:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |