제출 #1174157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174157		avighna	Naan (JOI19_naan)	C++20	5 / 100	1 ms	328 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;
  };

  std::vector<int> p(n);
  std::iota(p.begin(), p.end(), 0);
  do {
    auto sum1 = [&](int l, int r) {
      if (l > r) {
        return 0LL;
      }
      long long ans = pv[p[0]][r];
      if (l != 0) {
        ans -= pv[p[0]][l - 1];
      }
      return ans;
    };
    auto sum2 = [&](int l, int r) {
      if (l > r) {
        return 0LL;
      }
      long long ans = pv[p[1]][r];
      if (l != 0) {
        ans -= pv[p[1]][l - 1];
      }
      return ans;
    };

    auto idx1 =
        *std::ranges::partition_point(std::views::iota(0, l), [&](int i) {
          return n * sum1(0, i) < sum1(0, l - 1);
        });
    auto idx2 = l -
                *std::ranges::partition_point(
                    std::views::iota(0, l),
                    [&](int i) {
                      return n * sum2(l - i - 1, l - 1) < sum2(0, l - 1);
                    }) -
                1;
    if (idx1 > idx2) {
      continue;
    }
    if (idx1 < idx2) {
      std::cout << idx1 + 1 << " 1\n";
      for (auto &i : p) {
        std::cout << i + 1 << ' ';
      }
      std::cout << '\n';
      return 0;
    }
    // sum[0...idx1-1] + x * v[idx1] = sum[0...l-1] / n
    // x = (sum[0...l-1] - n sum[0...idx1-1]) / (v[idx1] * n)
    long long n1 = sum1(0, l - 1) - n * sum1(0, idx1 - 1);
    long long d1 = v[p[0]][idx1] * (long long)n;
    // sum[idx2+1...l-1] + x * v[idx2] = sum[0...l-1] / n
    // x = (sum[0...l-1] - n sum[idx2+1...l-1]) / (v[idx2] * n)
    long long n2 = sum2(0, l - 1) - n * sum2(idx2 + 1, l - 1);
    long long d2 = v[p[1]][idx2] * (long long)n;

    reduce(n1, d1);
    reduce(n2, d2);

    if (__int128_t(n1) * d2 + __int128_t(n2) * d1 > __int128_t(d1) * d2) {
      continue;
    }
    n1 += d1 * idx1;
    std::cout << n1 << ' ' << d1 << '\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: 0 / 24
• Subtask 3: 0 / 71