Submission #684678

#TimeUsernameProblemLanguageResultExecution timeMemory
684678peijarNaan (JOI19_naan)C++17
100 / 100
3437 ms118012 KiB
#include <bits/stdc++.h> #define int long long using namespace std; string to_string(string s) { return s; } template <typename T> string to_string(T v) { bool first = true; string res = "["; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "]"; return res; } void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << to_string(H); dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif struct Rational { int p, q; Rational() : p(0), q(1) {} Rational(int _p, int _q) : p(_p), q(_q) { int d = gcd(p, q); p /= d, q /= d; } Rational(int x) : p(x), q(1) {} Rational operator+(Rational other) const { return Rational(p * other.q + other.p * q, other.q * q); } Rational operator-(Rational other) const { return Rational(p * other.q - q * other.p, other.q * q); } Rational operator*(Rational other) const { return Rational(p * other.p, q * other.q); } Rational operator/(Rational other) const { return Rational(p * other.q, q * other.p); } bool operator<(Rational other) const { return (__int128)p * other.q < (__int128)q * other.p; } bool operator<=(Rational other) const { return !(other < *this); } }; signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int nbPersonnes, tailleGateau; cin >> nbPersonnes >> tailleGateau; vector<vector<int>> gain(nbPersonnes, vector<int>(tailleGateau)); for (int i = 0; i < nbPersonnes; ++i) for (int j = 0; j < tailleGateau; ++j) cin >> gain[i][j]; vector<Rational> need(nbPersonnes); for (int i = 0; i < nbPersonnes; ++i) { for (int j = 0; j < tailleGateau; ++j) need[i] = need[i] + gain[i][j]; need[i] = need[i] / nbPersonnes; } vector<vector<Rational>> cuts(nbPersonnes); for (int i = 0; i < nbPersonnes; ++i) { Rational rat; for (int j = 0; j < tailleGateau; ++j) { Rational taken(0); while (need[i] <= Rational(gain[i][j]) * (Rational(1) - taken) + rat) { Rational x = (need[i] - rat + taken * gain[i][j]) / gain[i][j]; cuts[i].push_back(Rational(j) + x); taken = x; rat = 0; } rat = rat + (Rational(1) - taken) * gain[i][j]; } assert((int)cuts[i].size() == nbPersonnes); } vector<int> perm; vector<bool> used(nbPersonnes); for (int i = 0; i < nbPersonnes; ++i) { int first = -1; for (int j = 0; j < nbPersonnes; ++j) if (!used[j] and (first == -1 or cuts[j][i] < cuts[first][i])) first = j; perm.push_back(first); used[first] = true; } for (int i = 0; i < nbPersonnes - 1; ++i) { auto [p, q] = cuts[perm[i]][i]; cout << p << ' ' << q << '\n'; } for (int x : perm) cout << x + 1 << ' '; cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...