Submission #702428

#TimeUsernameProblemLanguageResultExecution timeMemory
702428PixelCatNaan (JOI19_naan)C++14
29 / 100
119 ms262144 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...