Pietra - Code - Frações

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct frac {
   int n, d;

   void simplify() {
      int g = __gcd(n, d);
      n /= g; d /= g;
   }

   void printtt() {
      cout << n << '/' << d << "\n";
   }

   frac() {}
   frac(int _n, int _d) : n(_n), d(_d) { simplify(); }

};

bool operator<(const frac &a, const frac &b) {
   return a.n * b.d < b.n * a.d;
}

frac operator+(const frac &a, const frac &b) {
   frac f = frac( a.n * b.d + b.n * a.d, a.d * b.d );
   f.simplify();
   return f;
}

frac operator/(const frac &a, int d) {
   frac r = frac(a.n, a.d * d);
   r.simplify();
   return r;
}

int n, X, z, last;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

   cin >> n >> X >> z >> last;

   priority_queue<pair<frac, frac>> intervals;

   for(int i = 1; i < n; i++)  {
      int cur;
      cin >> cur;
      frac f(cur - last, 1);
      frac s(-last, 1);
      intervals.push({f, s}); // {size, start}
      last = cur;
   }

   vector<pair<int, int>> query(z);

   for(int i = 0; i < z; i++) {
      int k;
      cin >> k;
      query.push_back({k, i});
   }

   sort(query.begin(), query.end());

   vector<frac> ans(z);
   int cnt = 0;

   for(auto [k, i] : query) {

      while(cnt < k) {

         auto [f, s1] = intervals.top();
         intervals.pop();

         f = f / 2;

         s1.n *= -1;
         frac s2 = s1 + f;

         ans[i] = s2;

         s1.n *= -1;
         s2.n *= -1;

         intervals.push({f, s1});
         intervals.push({f, s2});

         cnt++;
      }

   }
   for(int i = 0; i < z; i++)
      ans[i].printtt();

    return 0;
}