제출 #1174134

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

  std::vector<int> p(n);
  std::iota(p.begin(), p.end(), 0);
  do {
    auto idx1 =
        *std::ranges::partition_point(std::views::iota(int(0), l), [&](int i) {
          return n * pv[p[0]][i] < pv[p[0]][l - 1];
        });
    auto idx2 =
        l -
        *std::ranges::partition_point(
            std::views::iota(int(0), l),
            [&](int i) {
              int j = l - i - 1;
              return n * (pv[p[1]][l - 1] - (j == 0 ? 0 : pv[p[1]][j - 1])) <
                     pv[p[1]][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;
    }
    // x = (v[n-1] - n v[0...idx1] + n v[idx1]) / (n v[idx1])
    long long n1 = pv[p[0]][l - 1] - (long long)n * pv[p[0]][idx1] +
                   (long long)n * v[p[0]][idx1];
    long long d1 = v[p[0]][idx1] * (long long)n;
    //  x = (v[n-1] - n*v[idx2...n-1] + n * v[idx2]) / (n * v[idx2])
    long long n2 = pv[p[1]][l - 1] - n * pv[p[0]][l - 1] +
                   (idx2 == 0 ? 0 : n * pv[p[0]][idx2 - 1]) + n * v[p[1]][idx2];
    long long d2 = n * v[p[0]][idx2];

    if (__int128_t(n1) * d2 > __int128_t(n2) * d1) {
      continue;
    }
    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()));
}

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