| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1092878 | Pannda | Naan (JOI19_naan) | C++17 | 0 ms | 0 KiB |
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;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
struct Fraction {
__int128 a = 0, b = 1;
bool operator<(const Fraction &other) const & {
return a * other.b < other.a * b;
}
bool operator<=(const Fraction &other) const & {
return !(other < *this);
}
Fraction operator*(const Fraction &other) const & {
__int128 A = a * other.a;
__int128 B = b * other.b;
__int128 G = abs(__gcd(A, B));
return {A / G, B / G};
}
Fraction operator+(const Fraction &other) const & {
__int128 B = b * other.b;
__int128 A = a * other.b + other.a * b;
__int128 G = abs(__gcd(A, B));
return {A / G, B / G};
}
Fraction operator-(Fraction other) {
other.a *= -1;
return (*this) + other;
}
};
int n, m;
cin >> n >> m;
vector<vector<int>> v(n, vector<int>(m));
vector<vector<int>> f(n, vector<int>(m + 1, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x;
cin >> x;
v[i][j] = x;
f[i][j + 1] = f[i][j] + x;
}
}
vector<Fraction> key;
vector<int> perm;
vector<bool> chosen(n, false);
Fraction cur = {0, 1};
vector<int> ptr(n, 0); // possible cut for i is in [ptr[i], ptr[i] + 1)
for (int t = 0; t < n - 1; t++) {
vector<pair<Fraction, int>> get = [&]() -> vector<pair<Fraction, int>> {
vector<pair<Fraction, int>> res;
for (int i = 0; i < n; i++) {
if (chosen[i]) continue;
Fraction nxt = [&]() -> Fraction {
auto F = [&](Fraction x) -> Fraction {
int j = x.a / x.b;
return Fraction{f[i][j], 1} + Fraction{v[i][j], 1} * Fraction{x.a % x.b, x.b};
};
Fraction req = Fraction{f[i][m], n};
Fraction Fcur = F(cur);
while (true) {
if (Fraction{f[i][ptr[i] + 1], 1} - Fcur <= req) { // then is not enough
ptr[i]++;
continue;
}
return Fraction{ptr[i], 1} + ( req + Fcur - Fraction{f[i][ptr[i]], 1}) * Fraction{1, v[i][ptr[i]]};
}
}();
res.push_back({nxt, i});
}
return res;
}();
auto [nxt, i] = *min_element(get.begin(), get.end());
key.push_back(nxt);
perm.push_back(i);
cur = nxt;
chosen[i] = true;
}
for (int i = 0; i < n; i++) {
if (!chosen[i]) perm.push_back(i);
}
for (Fraction frac : key) {
cout << (long long)frac.a << ' ' << (int)frac.b << '\n';
}
for (int i : perm) {
cout << i + 1 << ' ';
}
cout << '\n';
}