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 mod 998244353
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l%&&r<=sr
#define outside sr<l||r<sl
typedef long long ll;
int n, m;
ll mat[2002][2002];
ll presum[2002][2002];
pair<ll, ll> bol[2002][2002];
vector<pair<ll, ll> > ans;
vector<int> p;
pair<ll, ll> sum(pair<ll, ll> a, pair<ll, ll> b){
ll pay = a.first*b.second + a.second*b.first;
ll payda = a.second*b.second;
return mp(pay, payda);
}
pair<ll, ll> get(int i, ll pay, ll payda){
cout << "get(" << i << ", " << pay << ", " << payda << ")" << endl;
/*double ans = presum[i][(int)(pay/payda)-1];
ans += mat[i][(int)(pay/payda)]*((pay/payda) - (int)(pay/payda));
return ans;*/
return sum(mp(presum[i][(pay/payda)-1], 1), mp((pay%payda)*mat[i][pay/payda], payda));
}
pair<ll, ll> getmin(int i, pair<ll, ll> puan){
//cout << "getmin(" << i << ", " << puan.first << ", " << puan.second << ")" << endl;
if (presum[i][m-1] < (double)puan.first/(double)puan.second) return mp(-1, -1);
int l = -1;
int r = m-1;
while (l < r){
int m = (l+r+1)/2;
if (presum[i][m] > (double)puan.first/(double)puan.second) r = m-1;
else l = m;
}
//cout << bas(l) << endl;
if (l != -1 && presum[i][l] == (double)puan.first/(double)puan.second) return mp(l+1, 1);
puan = sum(puan, mp((l == -1) ? 0 : -presum[i][l], 1));
// mat[i][l+1]*oran = puan;
return sum(mp(l+1, 1), mp(puan.first, puan.second*mat[i][l+1]));
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < n; i++){
ll cur = 0;
for (int j = 0; j < m; j++){
cin >> mat[i][j];
cur += mat[i][j];
presum[i][j] = cur;
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
bol[j][i] = getmin(i, mp(presum[i][m-1]*(j+1), n));
//cout << bol[i][j].first << ", " << bol[i][j].second << " ";
}
//cout << endl;
}
//cout << endl;
bitset<2002> vis;
vis.reset();
for (int i = 0; i < n; i++){
double minn = 1000000000;
int mini = -1;
for (int j = 0; j < n; j++){
if (vis[j]) continue;
//cout << bas(i) << " " bas(j) << endl;
//cout << bas(minn) << " " << bas(bol[i][j].first) << bas(bol[i][j].second) << endl;
if ((double)bol[i][j].first / (double)bol[i][j].second < minn){
minn = (double)bol[i][j].first / (double)bol[i][j].second;
mini = j;
}
}
ans.pb(bol[i][mini]);
p.pb(mini+1);
vis[mini] = 1;
}
for (int i = 0; i < n-1; i++) cout << ans[i].first << " " << ans[i].second << endl;
for (int i = 0; i < p.size(); i++) cout << p[i] << " ";
}
Compilation message (stderr)
naan.cpp: In function 'int main()':
naan.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < p.size(); i++) cout << p[i] << " ";
~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |