#include <bits/stdc++.h>
struct Frac {
__int128_t n, d;
Frac(__int128_t _n, __int128_t _d) {
n = _n, d = _d;
__int128_t g = std::__gcd(n, d); n /= g, d /= g;
if (d < 0) n *= -1, d *= -1;
}
Frac(__int128_t _n) : Frac(_n, 1) {}
Frac() : Frac(0) {}
friend Frac abs(Frac F) { return Frac(abs(F.n), F.d); }
friend bool operator < (const Frac& l, const Frac& r) { return l.n * r.d < r.n * l.d; }
friend bool operator <= (const Frac& l, const Frac& r) { return l.n * r.d <= r.n * l.d; }
friend bool operator > (const Frac& l, const Frac& r) { return l.n * r.d > r.n * l.d; }
friend bool operator >= (const Frac& l, const Frac& r) { return l.n * r.d >= r.n * l.d; }
friend bool operator == (const Frac& l, const Frac& r) { return l.n == r.n && l.d == r.d; }
friend bool operator != (const Frac& l, const Frac& r) { return !(l == r); }
Frac operator - () const { return Frac(-n, d); }
friend Frac operator + (const Frac& l, const Frac& r) { return Frac(l.n * r.d + r.n * l.d, l.d * r.d); }
friend Frac operator - (const Frac& l, const Frac& r) { return Frac(l.n * r.d - r.n * l.d, l.d * r.d); }
friend Frac operator * (const Frac& l, const Frac& r) { return Frac(l.n * r.n, l.d * r.d); }
friend Frac operator * (const Frac& l, int r) { return l * Frac(r, 1); }
friend Frac operator * (int r, const Frac& l) { return l * r; }
friend Frac operator / (const Frac& l, const Frac& r) { return l * Frac(r.d, r.n); }
friend Frac operator / (const Frac& l, const int& r) { return l / Frac(r, 1); }
friend Frac operator / (const int& l, const Frac& r) { return Frac(l, 1) / r; }
friend Frac& operator += (Frac& l, const Frac& r) { return l = l + r; }
friend Frac& operator -= (Frac& l, const Frac& r) { return l = l - r; }
template <class T> friend Frac& operator *= (Frac& l, const T& r) { return l = l * r; }
template <class T> friend Frac& operator /= (Frac& l, const T& r) { return l = l / r; }
};
inline char gc() { // like getchar()
static char buf[1 << 16];
static size_t bc, be;
if (bc >= be) {
buf[0] = 0, bc = 0;
be = fread(buf, 1, sizeof(buf), stdin);
}
return buf[bc++]; // returns 0 on EOF
}
int read_int() {
int a, c;
while ((a = gc()) < 40);
if (a == '-') return -read_int();
while ((c = gc()) >= 48) a = a * 10 + c - 480;
return a - 48;
}
int main() {
using namespace std;
typedef __int128_t ll;
ios_base::sync_with_stdio(0);
int N, L;
cin >> N >> L;
vector<vector<ll>> V(N, vector<ll>(L));
for (int i = 0; i < N; i++)
for (int j = 0; j < L; j++) {
int x; x = read_int();
V[i][j] = x;
}
vector<vector<Frac>> split(N, vector<Frac>(N + 1));
for (int i = 0; i < N; i++) {
Frac need = 0;
for (int j = 0; j < L; j++)
need += V[i][j];
need /= N;
split[i][0] = 0;
Frac have = 0;
int it = 0;
Frac at = 0;
for (int j = 1; j <= N; j++) {
while (have < need) {
Frac add = (1 - at) * V[i][it];
if (have + add <= need) {
have += add;
at = 0;
it++;
} else {
Frac go = (need - have) / V[i][it];
have = need;
at += go;
}
}
split[i][j] = it + at;
have = 0;
}
}
const int INF = 1e9;
vector<Frac> splits(N);
vector<int> ord(N);
vector<bool> used(N);
for (int i = 1; i <= N - 1; i++) {
pair<Frac, int> best = {INF, INF};
for (int j = 0; j < N; j++)
if (!used[j])
best = min(best, {split[j][i], j});
splits[i - 1] = best.first;
ord[i - 1] = best.second;
used[best.second] = true;
}
for (int i = 0; i < N; i++) {
if (!used[i])
ord.back() = i;
}
for (int i = 1; i < N - 1; i++)
splits[i] = max(splits[i], splits[i - 1]);
for (int i = 0; i < N - 1; i++) {
assert(splits[i - 1] <= splits[i]);
}
for (int i = 0; i < N - 1; i++)
cout << (long long) splits[i].n << " " << (long long) splits[i].d << '\n';
for (int i = 0; i < N; i++)
cout << ord[i] + 1 << " ";
cout << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4049 ms |
364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4034 ms |
364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4049 ms |
364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
