| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 337395 | ryangohca | 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>
#define int long long
#define pii pair<int, int>
using namespace std;
struct fraction{
__int128_t num, den;
fraction(int num=0, int den=1):num(num), den(den){}
void normalize(){
int g = __gcd(num, den);
num /= g;
den /= g;
if(den < 0){
num = -num;
den = -den;
}
}
fraction operator-(){
return fraction{-num, den};
}
fraction operator+=(const fraction &b){
num = num*b.den + den*b.num;
den = den*b.den;
normalize();
return *this;
}
fraction operator-=(const fraction &b){
num = num*b.den - den*b.num;
den = den*b.den;
normalize();
return *this;
}
fraction operator*=(const fraction &b){
num = num*b.num;
den = den*b.den;
normalize();
return *this;
}
fraction operator/=(const fraction &b){
num = num*b.den;
den = den*b.num;
normalize();
return *this;
}
};
fraction operator+(fraction a, const fraction &b){return (a += b);}
fraction operator-(fraction a, const fraction &b){return (a -= b);}
fraction operator*(fraction a, const fraction &b){return (a *= b);}
fraction operator/(fraction a, const fraction &b){return (a /= b);}
bool operator==(const fraction &a, const fraction &b){return 1.0*a.num*b.den == 1.0*a.den*b.num;}
bool operator<(const fraction &a, const fraction &b){return 1.0*a.num*b.den < 1.0*a.den*b.num;}
bool operator>(const fraction &a, const fraction &b){return 1.0*a.num*b.den > 1.0*a.den*b.num;}
bool operator<=(const fraction &a, const fraction &b){return 1.0*a.num*b.den <= 1.0*a.den*b.num;}
bool operator>=(const fraction &a, const fraction &b){return 1.0*a.num*b.den >= 1.0*a.den*b.num;}
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';
}