#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
struct fraction {
__int128_t n, d;
fraction(__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;
}
fraction(__int128_t _n) : fraction(_n, 1) {}
fraction() : fraction(0) {}
friend fraction abs(fraction F) { return fraction(abs(F.n), F.d); }
friend bool operator < (const fraction& l, const fraction& r) { return l.n * r.d < r.n * l.d; }
friend bool operator <= (const fraction& l, const fraction& r) { return l.n * r.d <= r.n * l.d; }
friend bool operator > (const fraction& l, const fraction& r) { return l.n * r.d > r.n * l.d; }
friend bool operator >= (const fraction& l, const fraction& r) { return l.n * r.d >= r.n * l.d; }
friend bool operator == (const fraction& l, const fraction& r) { return l.n == r.n && l.d == r.d; }
friend bool operator != (const fraction& l, const fraction& r) { return !(l == r); }
fraction operator - () const { return fraction(-n, d); }
friend fraction operator + (const fraction& l, const fraction& r) { return fraction(l.n * r.d + r.n * l.d, l.d * r.d); }
friend fraction operator - (const fraction& l, const fraction& r) { return fraction(l.n * r.d - r.n * l.d, l.d * r.d); }
friend fraction operator * (const fraction& l, const fraction& r) { return fraction(l.n * r.n, l.d * r.d); }
friend fraction operator * (const fraction& l, int r) { return l * fraction(r, 1); }
friend fraction operator * (int r, const fraction& l) { return l * r; }
friend fraction operator / (const fraction& l, const fraction& r) { return l * fraction(r.d, r.n); }
friend fraction operator / (const fraction& l, const int& r) { return l / fraction(r, 1); }
friend fraction operator / (const int& l, const fraction& r) { return fraction(l, 1) / r; }
friend fraction& operator += (fraction& l, const fraction& r) { return l = l + r; }
friend fraction& operator -= (fraction& l, const fraction& r) { return l = l - r; }
template <class T> friend fraction& operator *= (fraction& l, const T& r) { return l = l * r; }
template <class T> friend fraction& operator /= (fraction& l, const T& r) { return l = l / r; }
};
int nums[2000][2000];
fraction cuts[2000][2000];
vector<fraction> confirmed;
vector<int> order;
bool ordered[2000];
inline int read() {
int x = 0;
char ch = getchar_unlocked();
while (ch < '0' || ch > '9') ch = getchar_unlocked();
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch & 15);
ch = getchar_unlocked();
}
return x;
}
main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n = read(), l = read();
fraction zero = fraction(0, 1), one = fraction(1, 1);
for (int i = 0; i < n; i++){
fraction need;
for (int j = 0; j < l; j++) {
nums[i][j] = read();
need += fraction(nums[i][j], 1);
}
need /= fraction(n, 1);
fraction curr, prevleft;
int idx = 0;
for (int j = 1; j < n; j++){
while (need > curr){
fraction willtake = (one - prevleft) * fraction(nums[i][idx], 1);
if (curr + willtake <= need){
curr += willtake;
idx++;
prevleft = zero;
} else {
prevleft = (need - curr) / fraction(nums[i][idx], 1);
curr = need;
break;
}
}
cuts[i][j] = fraction(idx, 1) + prevleft;
curr = fraction(0, 1);
}
}
for (int i = 1; i < n; i++){ // cut i
pair<fraction, int> giveCut = {fraction(1e9, 1), -1};
for (int j = 0; j < n; j++){ // person j
if (!ordered[j]) {
pair<fraction, int> other = {cuts[j][i], j};
giveCut = min(giveCut, other);
}
}
ordered[giveCut.second] = true;
confirmed.push_back(giveCut.first);
order.push_back(giveCut.second);
}
for (int i = 0; i < n; i++){
if (!ordered[i]) order.push_back(i);
}
for (fraction i : confirmed){
cout << i.num << ' ' << i.den << '\n';
}
for (auto i : order) cout << i + 1 << ' ';
cout << '\n';
}
Compilation message
naan.cpp: In function 'fraction abs(fraction)':
naan.cpp:14:62: error: call of overloaded 'abs(__int128&)' is ambiguous
14 | friend fraction abs(fraction F) { return fraction(abs(F.n), F.d); }
| ^
In file included from /usr/include/c++/9/bits/std_abs.h:38,
from /usr/include/c++/9/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from naan.cpp:1:
/usr/include/stdlib.h:837:12: note: candidate: 'int abs(int)'
837 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
| ^~~
In file included from /usr/include/c++/9/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from naan.cpp:1:
/usr/include/c++/9/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
79 | abs(long double __x)
| ^~~
/usr/include/c++/9/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
75 | abs(float __x)
| ^~~
/usr/include/c++/9/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
71 | abs(double __x)
| ^~~
/usr/include/c++/9/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
61 | abs(long long __x) { return __builtin_llabs (__x); }
| ^~~
/usr/include/c++/9/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
56 | abs(long __i) { return __builtin_labs(__i); }
| ^~~
naan.cpp: At global scope:
naan.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
51 | main(){
| ^
naan.cpp: In function 'int main()':
naan.cpp:97:19: error: 'struct fraction' has no member named 'num'
97 | cout << i.num << ' ' << i.den << '\n';
| ^~~
naan.cpp:97:35: error: 'struct fraction' has no member named 'den'
97 | cout << i.num << ' ' << i.den << '\n';
| ^~~
