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 fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
int N, L;
int chk[2010];
ll V[2010][2010], S[2010];
vector<pll> ar[2010];
vector<pair<pll, int> > VP[2010];
vim ans;
bool cmp(pll a, pll b) {return a.fi*b.se<b.fi*a.se;}
bool cmp1(pair<pll, int> a, pair<pll, int> b) {return a.fi.fi*b.fi.se<=b.fi.fi*a.fi.se;}
int main() {
scanf("%d %d", &N, &L);
for (int i=1; i<=N; i++) for (int j=1; j<=L; j++) {
scanf("%lld", &V[i][j]);
V[i][j]*=N;
S[i]+=V[i][j];
}
ll s;
for (int i=1; i<=N; i++) {
s=0;
ar[i].push_back({0,1});
for (int j=1, k=1; j<=L; j++) {
s+=V[i][j];
while (k<=N && k*(S[i]/N)<=s) {
ar[i].push_back({(j-1)*V[i][j]+k*(S[i]/N)-(s-V[i][j]) , V[i][j]});
k++;
}
}
ar[i].push_back({L, 1});
}
pll lst={0, 1};
for (int i=0; i<N; i++) {
for (int j=1; j<=N; j++) {
if (chk[j]) continue;
int lb=lower_bound(all(ar[j]), lst, cmp)-ar[j].begin();
VP[i].push_back({ar[j][lb+1], j});
}
sort(all(VP[i]), cmp1);
if (i!=N-1) printf("%lld %lld\n", VP[i][0].fi.fi, VP[i][0].fi.se);
ans.push_back(VP[i][0].se);
chk[VP[i][0].se]=1;
lst=VP[i][0].fi;
}
for (int i:ans) printf("%d ", i);
puts("");
return 0;
}
Compilation message (stderr)
naan.cpp: In function 'int main()':
naan.cpp:25: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:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &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... |