이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 p * other.q < 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];
}
dbg(i);
for (auto [p, q] : cuts[i])
dbg(p, q);
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;
}
컴파일 시 표준 에러 (stderr) 메시지
naan.cpp: In function 'int main()':
naan.cpp:94:15: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
94 | for (auto [p, q] : cuts[i])
| ^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |