Submission #332663

#TimeUsernameProblemLanguageResultExecution timeMemory
33266312tqianNaan (JOI19_naan)C++17
29 / 100
4074 ms167788 KiB
#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; } }; 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++) { long long x; cin >> x; 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) { if (have + (1 - at) * V[i][it] <= need) { have += (1 - at) * V[i][it]; at = 0; it++; } else { Frac go = (need - have) / V[i][it]; have += go * V[i][it]; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...