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;
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;
struct frac{
ll A;
ll B;
void normalize(){
ll g = __gcd(A, B);
A /= g;
B /= g;
}
frac operator+ (frac y){
frac T = {A * y.B + B * y.A, B * y.B};
T.normalize();
return T;
}
frac operator- (frac y){
frac T = {A * y.B - B * y.A, B * y.B};
T.normalize();
return T;
}
bool operator< (frac y){
return (A * y.B - B * y.A < 0);
}
};
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;
for(int i = 1; i <= n; i ++ ){
need[i] = {0, n};
for(int j = 1; j <= m ; j ++ ){
cin >> V[i][j];
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 = calc(i, {j, 1});
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 << low.A << " " << 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 (stderr)
naan.cpp: In function 'int main()':
naan.cpp:72:10: warning: unused variable 'cur' [-Wunused-variable]
72 | frac cur;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |