Submission #1174177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174177		avighna	Naan (JOI19_naan)	C++20	29 / 100	4094 ms	2376 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());
  }

  auto reduce = [&](long long &num, long long &den) {
    int d = std::gcd(num, den);
    num /= d, den /= d;
    if (num < 0 and den < 0) {
      num *= -1, den *= -1;
    }
  };

  std::vector<int> p(n);
  std::iota(p.begin(), p.end(), 0);
  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, int num, int den) {
    int w = num / den;
    long long full = sum(i, 0, w - 1);
    num -= w * den;
    return std::pair<long long, long long>({full * den + num * v[i][w], den});
  };
  do {
    std::vector<std::pair<long long, long long>> ans;
    std::pair<long long, long long> x = {0, 1};
    bool good = true;
    for (auto &i : p) {
      auto [num, den] = sum_f(i, x.first, x.second);
      reduce(num, den);
      auto idx =
          *std::ranges::partition_point(std::views::iota(0, l), [&](int j) {
            return __int128_t(n) * (sum(i, 0, j) * den - num) <
                   __int128_t(sum(i, 0, l - 1)) * den;
          });
      if (idx == l) {
        good = false;
        break;
      }
      // sum[0...idx-1] - sum_f[0...x] + x * v[idx] = sum[0...l-1] / n
      // x = (sum[0...l-1]*den + n*num - n*sum[0...idx-1]*den) / (n *
      // v[idx]*den)
      auto p1 = sum(i, 0, l - 1);
      auto p2 = sum(i, 0, idx - 1);
      long long _n =
          sum(i, 0, l - 1) * den - sum(i, 0, idx - 1) * den * n + num * n;
      long long _d = n * v[i][idx] * den;
      reduce(_n, _d);
      _n += _d * idx;
      reduce(_n, _d);
      if (x.first != 0) {
        ans.push_back(x);
      }
      x = {_n, _d};
    }
    if (!good) {
      continue;
    }
    for (auto &i : ans) {
      std::cout << i.first << ' ' << i.second << '\n';
    }
    for (auto &i : p) {
      std::cout << i + 1 << ' ';
    }
    std::cout << '\n';
    return 0;
  } while (std::next_permutation(p.begin(), p.end()));
  std::cout << "-1\n";
}

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