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 For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
struct Frac {
__int128_t x, y;
Frac(int _x = 0, int _y = 1) {
x = _x; y = _y;
simp();
}
void simp() {
int g = __gcd(x, y);
x /= g; y /= g;
}
};
Frac operator-(const Frac &a) {
return Frac(-a.x, a.y);
}
Frac operator+(const Frac &a, const Frac &b) {
return Frac(a.x * b.y + a.y * b.x, a.y * b.y);
}
Frac operator-(const Frac &a, const Frac &b) {
return a + (-b);
}
Frac operator*(const Frac &a, const Frac &b) {
return Frac(a.x * b.x, a.y * b.y);
}
Frac operator/(const Frac &a, const Frac &b) {
return Frac(a.x * b.y, a.y * b.x);
}
bool operator==(const Frac &a, const Frac &b) {
return a.x * b.y == a.y * b.x;
}
bool operator<(const Frac &a, const Frac &b) {
return a.x * b.y < a.y * b.x;
}
bool operator>(const Frac &a, const Frac &b) {
return b < a;
}
bool operator<=(const Frac &a, const Frac &b) {
return a < b || a == b;
}
bool operator>=(const Frac &a, const Frac &b) {
return a > b || a == b;
}
ostream& operator<<(ostream& os, const Frac &a) {
os << (LL)a.x << "/" << (LL)a.y;
return os;
}
const int MAXN = 2010;
struct Meow {
int v[MAXN];
Frac tar;
Frac inq[MAXN];
Frac rem[MAXN];
int pos_r, pos_l;
Frac now;
bool used;
void init(int n, int l) {
used = false;
tar = Frac();
For(i, 1, l) {
cin >> v[i];
tar.x += v[i];
rem[i] = Frac(1);
}
tar = tar / n;
pos_r = 1; pos_l = 1;
now = Frac(0);
push(1, Frac(0));
}
void push(int p0, Frac par) {
while(pos_l < p0) {
now = now - inq[pos_l] * v[pos_l];
pos_l++;
}
// cout << rem[pos_r] << " " << tar << " " << now << "\n" << flush;
Frac t = inq[pos_l] + rem[pos_r] + par - 1;
inq[pos_l] = inq[pos_l] - t;
now = now - t * v[pos_l];
while(now + rem[pos_r] * v[pos_r] < tar) {
now = now + rem[pos_r] * v[pos_r];
inq[pos_r] = inq[pos_r] + rem[pos_r];
rem[pos_r] = 0;
pos_r++;
}
t = (tar - now) / v[pos_r];
assert(t <= rem[pos_r]);
rem[pos_r] = rem[pos_r] - t;
inq[pos_r] = inq[pos_r] + t;
now = tar;
}
pair<int, Frac> get_front() {
return make_pair(pos_r, 1 - rem[pos_r]);
}
} meow[MAXN];
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
// nyanyanyanyanya
int n, l; cin >> n >> l;
// assert(n <= 6);
For(i, 1, n) meow[i].init(n, l);
vector<int> ans;
For(i, 1, n - 1) {
pair<int, Frac> front(l + 1, 0);
int min_id = -1;
For(j, 1, n) if(!meow[j].used) {
if(meow[j].get_front() < front) {
front = meow[j].get_front();
min_id = j;
}
// auto p = meow[j].get_front();
// cout << j << " : " << p.F << " - " << p.S << "\n" << flush;
}
ans.eb(min_id);
meow[min_id].used = true;
For(j, 1, n) if(!meow[j].used) {
meow[j].push(front.F, front.S);
}
front.S = front.F - 1 + front.S;
cout << (LL)front.S.x << " " << (LL)front.S.y << "\n";
}
for(auto &i:ans) cout << i << " ";
For(i, 1, n) if(!meow[i].used) cout << i << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |