#include <bits/stdc++.h>
using namespace std;
using lint = long long;
lint gcd(lint x, lint y) {
return min(x, y) == 0 ? max(x, y) : gcd(y, x % y);
}
lint lcm(lint x, lint y) {
return (x / gcd(x, y)) * y;
}
struct Rational { // rational number of x/y
lint x, y;
Rational(lint x = 0, lint y = 1) {
lint g = gcd(x, y);
x /= g;
y /= g;
this->x = x;
this->y = y;
}
Rational operator + (const Rational &o) const {
Rational a = *this, b = o;
Rational res;
lint c = a.x / a.y + b.x / b.y;
a.x %= a.y;
b.x %= b.y;
res.y = lcm(a.y, b.y);
res.x = (a.x * (res.y / a.y)) + (b.x * (res.y / b.y)) + (c * res.y);
return res;
}
bool operator < (const Rational &o) const {
if ((x / y) < (o.x / o.y)) return true;
if ((x / y) > (o.x / o.y)) return false;
return (x % y) * o.y < (o.x % o.y) * y;
}
};
int N, L;
vector<vector<int>> V;
vector<lint> sum;
vector<vector<Rational>> split;
vector<Rational> X;
vector<int> P;
void Read() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> L;
V.assign(N, vector<int>(L));
for (int i = 0; i < N; i++) {
for (int j = 0; j < L; j++) {
cin >> V[i][j];
}
}
}
void Write() {
for (int i = 0; i + 1 < N; i++) {
cout << X[i].x << " " << X[i].y << "\n";
}
for (int i = 0; i < N; i++) {
cout << P[i] << " \n"[i == N - 1];
}
}
void Solve() {
split.resize(N);
sum.resize(N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < L; j++) {
sum[i] += V[i][j];
}
}
for (int i = 0; i < N; i++) {
lint current = 0;
int p = 0;
for (int j = 1; j <= N - 1; j++) {
while ((current + V[i][p]) * N <= sum[i] * j) {
current += V[i][p++];
}
lint rest = sum[i] * j - current * N;
split[i].emplace_back((Rational(p) + Rational(rest, N * V[i][p])));
}
}
vector<bool> taken(N, false);
for (int c = 0; c < N; c++) {
int minim = -1;
for (int i = 0; i < N; i++) {
if (taken[i]) continue;
if (minim == -1 || split[i][c] < split[minim][c]) {
minim = i;
}
}
taken[minim] = true;
P.emplace_back(minim + 1);
if (c + 1 < N) {
X.emplace_back(split[minim][c]);
}
}
}
int main() {
Read();
Solve();
Write();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
4 ms |
256 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
6 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
4 ms |
256 KB |
Output is correct |
28 |
Correct |
5 ms |
384 KB |
Output is correct |
29 |
Correct |
5 ms |
384 KB |
Output is correct |
30 |
Correct |
5 ms |
384 KB |
Output is correct |
31 |
Correct |
5 ms |
384 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
33 |
Correct |
5 ms |
384 KB |
Output is correct |
34 |
Correct |
6 ms |
384 KB |
Output is correct |
35 |
Correct |
5 ms |
384 KB |
Output is correct |
36 |
Correct |
5 ms |
384 KB |
Output is correct |
37 |
Correct |
5 ms |
384 KB |
Output is correct |
38 |
Correct |
5 ms |
384 KB |
Output is correct |
39 |
Correct |
5 ms |
384 KB |
Output is correct |
40 |
Correct |
5 ms |
384 KB |
Output is correct |
41 |
Correct |
5 ms |
384 KB |
Output is correct |
42 |
Correct |
6 ms |
384 KB |
Output is correct |
43 |
Correct |
94 ms |
10232 KB |
Output is correct |
44 |
Correct |
546 ms |
51704 KB |
Output is correct |
45 |
Correct |
238 ms |
23032 KB |
Output is correct |
46 |
Correct |
29 ms |
2552 KB |
Output is correct |
47 |
Correct |
353 ms |
30072 KB |
Output is correct |
48 |
Correct |
723 ms |
65912 KB |
Output is correct |
49 |
Correct |
169 ms |
17400 KB |
Output is correct |
50 |
Correct |
893 ms |
79356 KB |
Output is correct |
51 |
Correct |
327 ms |
32392 KB |
Output is correct |
52 |
Correct |
763 ms |
73080 KB |
Output is correct |
53 |
Correct |
709 ms |
65788 KB |
Output is correct |
54 |
Correct |
5 ms |
384 KB |
Output is correct |
55 |
Correct |
368 ms |
38240 KB |
Output is correct |
56 |
Correct |
449 ms |
44792 KB |
Output is correct |
57 |
Correct |
368 ms |
38136 KB |
Output is correct |
58 |
Correct |
646 ms |
64376 KB |
Output is correct |
59 |
Correct |
362 ms |
37368 KB |
Output is correct |
60 |
Correct |
1016 ms |
102392 KB |
Output is correct |
61 |
Correct |
1012 ms |
102520 KB |
Output is correct |
62 |
Correct |
1092 ms |
102264 KB |
Output is correct |
63 |
Correct |
1058 ms |
102648 KB |
Output is correct |
64 |
Correct |
1022 ms |
102648 KB |
Output is correct |
65 |
Correct |
1035 ms |
89208 KB |
Output is correct |
66 |
Correct |
1006 ms |
89208 KB |
Output is correct |
67 |
Correct |
946 ms |
89080 KB |
Output is correct |
68 |
Correct |
420 ms |
48520 KB |
Output is correct |
69 |
Correct |
394 ms |
45692 KB |
Output is correct |
70 |
Correct |
510 ms |
59000 KB |
Output is correct |
71 |
Correct |
605 ms |
69368 KB |
Output is correct |