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 pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 2000;
ll N, L;
ll arr[MAX_N+1][MAX_N+1];
ll sum[MAX_N+1];
vector<pll> vt[MAX_N+1];
bool vst[MAX_N+1];
vector<pll> ans;
vector<int> ans2;
bool calc(pll a, pll b){
a.first /= L; b.first /= L;
a.second /= N; b.second /= N;
return (a.first * b.second > a.second * b.first);
}
int main(){
scanf("%lld%lld", &N, &L);
for(int i=1; i<=N; i++){
for(int j=1; j<=L; j++){
scanf("%lld", &arr[i][j]);
sum[i]+=arr[i][j];
}
int now = 1;
ll S = 0;
for(int j=1; j<=L; j++){
while(1){
//cout<<S<<" "<<now<<endl;
if((S+arr[i][j]) * N <= now * sum[i]){
break;
}
pll p;
p.first = sum[i] * now - S * N + (j-1) * N * arr[i][j];
p.second = N * arr[i][j];
vt[i].pb(p);
//cout<<p.first<<" "<<p.second<<endl;
now++;
}
S += arr[i][j];
}
}
for(int i=0; i<N-1; i++){
pll prv = {L, 0};
int idx=0;
for(int j=1; j<=N; j++){
//cout<<prv.first<<" "<<prv.second<<" "<<vt[j][i].first<<" "<<vt[j][i].second<<endl;
if(!vst[j] && calc(prv, vt[j][i])){
idx = j; prv = vt[j][i];
}
}
//cout<<idx<<endl;
vst[idx] = true;
ans.pb(prv);
ans2.pb(idx);
}
for(int j=1; j<=N; j++){
if(!vst[j]){
ans2.pb(j);
break;
}
}
for(int i=0; i<ans.size(); i++){
printf("%lld %lld\n", ans[i].first, ans[i].second);
}
for(int i=0; i<ans2.size(); i++){
printf("%d ", ans2[i]);
}
return 0;
}
Compilation message (stderr)
naan.cpp: In function 'int main()':
naan.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<ans.size(); i++){
~^~~~~~~~~~~
naan.cpp:90:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<ans2.size(); i++){
~^~~~~~~~~~~~
naan.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &N, &L);
~~~~~^~~~~~~~~~~~~~~~~~~~
naan.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &arr[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... |