Submission #1174316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174316		avighna	Naan (JOI19_naan)	C++20	29 / 100	38 ms	2628 KiB

naan

#include <bits/stdc++.h>

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

  int n, l;
  std::cin >> n >> l;
  std::vector v(n, std::vector<int>(l)), pv(n, std::vector<int>(l));
  for (int i = 0; i < n; ++i) {
    for (auto &j : v[i]) {
      std::cin >> j;
    }
    std::partial_sum(v[i].begin(), v[i].end(), pv[i].begin());
  }

  struct Fraction {
    __int128_t num, den;

    Fraction() : num(0), den(1) {}
    Fraction(long long x) : num(x), den(1) {}
    Fraction(long long num, long long den) : num(num), den(den) { reduce(); }
    Fraction(__int128_t num, __int128_t den) : num(num), den(den) { reduce(); }

    void reduce() {
      std::function<__int128_t(__int128_t, __int128_t)> gcd;
      gcd = [&](__int128_t a, __int128_t b) {
        while (b != 0) {
          auto temp = b;
          b = a % b;
          a = temp;
        }
        return a;
      };
      __int128_t d = gcd(num > 0 ? num : -num, den > 0 ? den : -den);
      num /= d, den /= d;
      if (num < 0 and den < 0) {
        num *= -1, den *= -1;
      }
    }

    Fraction operator+(const Fraction &other) const {
      Fraction ans;
      ans.num = num * other.den + other.num * den;
      ans.den = den * other.den;
      ans.reduce();
      return ans;
    }
    Fraction operator-(const Fraction &other) const {
      return operator+({-other.num, other.den});
    }
    Fraction operator*(const Fraction &other) const {
      Fraction ans;
      ans.num = num * other.num;
      ans.den = den * other.den;
      ans.reduce();
      return ans;
    }

    bool operator<(const Fraction &other) const {
      return num * other.den < other.num * den;
    }
  };

  auto sum = [&](int i, int l, int r) {
    if (l > r) {
      return 0LL;
    }
    long long ans = pv[i][r];
    if (l != 0) {
      ans -= pv[i][l - 1];
    }
    return ans;
  };
  auto sum_f = [&](int i, Fraction x) {
    int w = x.num / x.den;
    long long full = sum(i, 0, w - 1);
    x.num -= w * x.den;
    return Fraction(full * x.den + x.num * v[i][w], x.den);
  };
  std::vector<Fraction> ans;
  std::vector<int> p;
  std::set<int> st;
  for (int i = 0; i < n; ++i) {
    st.insert(i);
  }
  Fraction prev = 0;
  while (!st.empty()) {
    std::pair<Fraction, int> min = {l + 1, -1};
    for (auto &i : st) {
      auto prev_sum = sum_f(i, prev);
      auto idx =
          *std::ranges::partition_point(std::views::iota(0, l), [&](int j) {
            return Fraction(sum(i, 0, j)) - prev_sum <
                   Fraction(sum(i, 0, l - 1), n);
          });
      Fraction x =
          Fraction(1LL, v[i][idx]) * (Fraction(sum(i, 0, l - 1), n) + prev_sum -
                                      Fraction(sum(i, 0, idx - 1)));
      min = std::min(min, {x + Fraction(idx), i});
    }
    p.push_back(min.second);
    if (prev.num != 0) {
      ans.push_back(prev);
    }
    prev = min.first;
    st.erase(min.second);
  }
  for (auto &[a, b] : ans) {
    std::cout << (long long)a << ' ' << (long long)b << '\n';
  }
  for (auto &i : p) {
    std::cout << i + 1 << ' ';
  }
  std::cout << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71