#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 2010;
const ll C = (ll)1e18;
struct frac{
ll A;
ll B;
frac operator+ (frac y){
return {A * y.B + B * y.A, B * y.B};
}
frac operator- (frac y){
return {A * y.B - B * y.A, B * y.B};
}
bool operator< (frac y){
if(A/B == y.A/y.B){
ll common = A/B;
ll temp0 = A - B * common;
ll temp1 = y.A - y.B * common;
return (temp0 * y.B - B * temp1 < 0);
}
else{
return A/B < y.A/y.B;
}
}
};
ll V[N][N];
ll S[N][N];
int m;
frac calc(int id, frac P){
int las = P.A / P.B;
frac Y = {S[id][las], 1};
frac add = (P - (frac){las, 1});
add.A *= V[id][las + 1];
Y = Y + add;
return Y;
}
frac need[N];
bool use[N];
int pi[N];
int main(){
fastIO;
//freopen("in.txt", "r", stdin);
int n;
cin >> n >> m;
int vv;
for(int i = 1; i <= n; i ++ ){
need[i] = {0, n};
for(int j = 1; j <= m ; j ++ ){
cin >> vv;
V[i][j] = vv;
need[i].A += V[i][j];
S[i][j] = V[i][j] + S[i][j - 1];
}
pi[i] = -1;
}
frac las = {0, 1};
frac tis;
frac nx;
frac cur;
frac low;
int idx;
frac S;
ll X;
for(int it = 1; it < n; it ++ ){
low = {m, 1};
idx = -1;
for(int i = 1; i <= n; i ++ ){
if(!use[i]){
tis = calc(i, las);
for(int j = 1; j <= m; j ++ ){
nx = {S[i][j], 1ll};
if(tis < nx){
if(need[i] < nx - tis){
S = nx - tis;
S = S - need[i];
S.A *= (ll)n;
X = S.A / S.B;
tis = (frac){j, 1} - (frac){X, n * 1ll * V[i][j]};
if(tis < low){
low = tis;
idx = i;
}
break;
}
}
}
}
}
pi[it] = idx;
use[idx]=true;
las = low;
cout << (long long)low.A << " " << (long long)low.B << "\n";
}
for(int i = 1; i <= n; i ++ ){
if(!use[i]){
pi[n]=i;
}
}
for(int i = 1; i <= n; i ++ ){
cout << pi[i] << " ";
}
cout << "\n";
return 0;
}
Compilation message
naan.cpp: In function 'int main()':
naan.cpp:87:28: error: no match for 'operator[]' (operand types are 'frac' and 'int')
87 | nx = {S[i][j], 1ll};
| ^
naan.cpp:87:39: error: no match for 'operator=' (operand types are 'frac' and '<brace-enclosed initializer list>')
87 | nx = {S[i][j], 1ll};
| ^
naan.cpp:16:8: note: candidate: 'constexpr frac& frac::operator=(const frac&)'
16 | struct frac{
| ^~~~
naan.cpp:16:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const frac&'
naan.cpp:16:8: note: candidate: 'constexpr frac& frac::operator=(frac&&)'
naan.cpp:16:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'frac&&'
naan.cpp:74:10: warning: unused variable 'cur' [-Wunused-variable]
74 | frac cur;
| ^~~
